141 环形链表
如下图所示:
- 没有环时:
- 当
fast != nullptr时,fast和slow不会相遇 - 当
fast == nullptr时,slow还没走到链表末尾,fast和slow不会相遇 - 当
fast == nullptr后,slow走到链表末尾时,fast和slow相遇,此时fast = slow = nullptr
- 当
- 有环时:
fast不可能为nullptrfast和slow相遇,但不一定在链表相交处相遇
由以上分析,可以得出:
- 如果最终
fast == nullptr,则没有环。这一步在程序中进一步表述为:循环停止条件fast == nullptr || fast->next == nullptrfast == nullptr,空链表或者快慢指针到达链表末尾仍未相遇fast->next == nullptr,链表只有一个元素,且没有成环
- 如果
fast != nullptr且fast == slow,则有环
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
// 如果有环,fast永远不为nullptr
// fast和slow一定会相遇
if(fast == slow)
return true;
}
// 如果fast == nullptr,说明链表没有环
return false;
}
};