判断链表是否有环c 代码,遍历链表法
时间: 2024-08-18 18:01:24 浏览: 26
判断链表是否有环的一种常见方法是使用快慢指针(也称龟兔赛跑法)。这种方法涉及到两个指针,一个普通节点步进(每次移动一步),另一个快速节点每两步前进一次。如果链表有环,那么快指针最终会追上慢指针;如果没有环,则快指针会在到达链表尾部后返回 null。
以下是使用 C 语言实现的一个简单示例:
```c
#include <stdbool.h>
#include <stdlib.h>
// 链表节点结构
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 检查链表是否有环
bool hasCycle(ListNode* head) {
if (head == NULL || head->next == NULL) {
return false; // 空链表或者只有一个节点都没有环
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return false; // 如果快指针到了头或空指针,说明无环
}
slow = slow->next;
fast = fast->next->next;
}
return true; // 如果慢指针和快指针相遇,说明有环
}