用指针判断链表是否有环,写出详细的C语言代码
时间: 2024-02-18 09:05:14 浏览: 72
判断单链表中是否存在环
判断链表是否有环,可以使用快慢指针的方法。具体来说,可以用两个指针,一个指针每次向前移动1个节点,另一个指针每次向前移动2个节点。如果存在环,那么这两个指针最终一定会相遇。
以下是详细的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 判断链表是否有环
bool hasCycle(struct ListNode *head) {
if (head == NULL) {
return false;
}
struct ListNode *slow = head;
struct ListNode *fast = head->next;
while (fast != NULL && fast->next != NULL) {
if (slow == fast) {
return true;
}
slow = slow->next;
fast = fast->next->next;
}
return false;
}
int main() {
// 创建链表
struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
head->val = 1;
head->next = NULL;
struct ListNode *node1 = (struct ListNode *)malloc(sizeof(struct ListNode));
node1->val = 2;
head->next = node1;
struct ListNode *node2 = (struct ListNode *)malloc(sizeof(struct ListNode));
node2->val = 3;
node1->next = node2;
struct ListNode *node3 = (struct ListNode *)malloc(sizeof(struct ListNode));
node3->val = 4;
node2->next = node3;
// 构造环
node3->next = node1;
// 判断链表是否有环
if (hasCycle(head)) {
printf("链表有环\n");
} else {
printf("链表无环\n");
}
return 0;
}
```
在上面的代码中,我们先创建了一个包含4个节点的链表,并构造了一个环。然后使用`hasCycle()`函数判断链表是否有环,最终输出结果。
阅读全文