帮我输出一份关于c语言的快慢指针的经验案例教程
时间: 2024-02-18 12:00:52 浏览: 21
当我们在编写 C 语言程序时,经常会用到指针,而快慢指针(双指针)则是其中比较常见的一种。在下面的实例中,我将演示如何使用快慢指针来解决 LeetCode 上的一道题目。
题目描述:给定一个链表,判断它是否有环。
常规方法是使用哈希表或者标记法,但是我们也可以使用快慢指针来解决这个问题。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 链表结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 创建链表
struct ListNode* createList(int a[], int n) {
struct ListNode *head, *p, *q;
head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = a[0];
head->next = NULL;
p = head;
for (int i = 1; i < n; i++) {
q = (struct ListNode*)malloc(sizeof(struct ListNode));
q->val = a[i];
q->next = NULL;
p->next = q;
p = q;
}
return head;
}
// 判断链表是否有环
bool hasCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return false;
}
struct ListNode *fast = head->next;
struct ListNode *slow = head;
while (fast != slow) {
if (fast == NULL || fast->next == NULL) {
return false;
}
fast = fast->next->next;
slow = slow->next;
}
return true;
}
int main() {
int a[] = {3,2,0,-4};
int n = sizeof(a) / sizeof(int);
struct ListNode *head = createList(a, n);
// 使链表有环
head->next->next->next->next = head->next;
if (hasCycle(head)) {
printf("链表有环\n");
} else {
printf("链表没有环\n");
}
return 0;
}
```
在上面的代码中,我们首先定义了一个链表结构体 `struct ListNode`,然后通过 `createList` 函数创建了一个链表。接下来,我们定义了 `hasCycle` 函数来判断链表是否有环。在函数中,我们定义了两个指针,一个指针 `fast` 每次移动两个节点,另一个指针 `slow` 每次移动一个节点。如果链表有环,则 `fast` 指针最终会追上 `slow` 指针,否则 `fast` 指针会到达链表的末尾。
最后,我们在 `main` 函数中调用 `hasCycle` 函数来判断链表是否有环,并输出结果。
总结:快慢指针是一种比较常见的指针应用方法,可以用来解决多种问题,比如判断链表是否有环。