C编写一个函数,判断链表中是否有环
时间: 2024-05-05 14:15:19 浏览: 7
以下是一种基于快慢指针的方法来判断链表中是否有环。
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
bool hasCycle(ListNode *head) {
// 如果链表为空或只有一个节点,则一定没有环
if (!head || !head->next) {
return false;
}
// 定义快慢指针
ListNode *slow = head;
ListNode *fast = head->next;
// 当快指针能够继续向前,且慢指针没有追上快指针时
while (fast && fast->next && slow != fast) {
slow = slow->next;
fast = fast->next->next;
}
// 如果快指针已经到达链表末尾,说明链表没有环
if (!fast || !fast->next) {
return false;
}
// 如果慢指针追上了快指针,说明链表有环
return true;
}
```
该函数的基本思路是,使用两个指针slow和fast,开始时它们都指向链表的头部。slow每次向后移动一个节点,而fast每次向后移动两个节点。如果链表中有环,那么fast指针一定会在某个时刻追上slow指针。如果链表中没有环,那么fast指针会在到达链表末尾之前先到达NULL节点。