Linked List Cycle
最后更新于：2022-04-01 22:55:53
**一. 题目描述**
Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
**二. 题目分析**
题目的意思是给定一个链表的头指针，快速判断一个链表是不是有环，如果有环，返回环的起始位置。该题的经典做法是使用两个指针，两个指针均指向头结点，其中一个是快指针，一次走两步；另一个是慢指针，一次只走一步，当两个指针相遇时，证明有环。这种方法的时间复杂度为`O(n)`，空间复杂度`O(1)`，这里需要考虑一些特殊情况：
* 空链表无环
* 链表只有一个节点时可能构成自环
**三. 示例代码**
~~~
#include
struct ListNode
{
int value;
ListNode* next;
ListNode(int x) :value(x), next(NULL){}
};
class Solution
{
public:
bool hasCycle(ListNode *head)
{
if (head == nullptr || head->next == nullptr)
return false;
ListNode* fast = head;
ListNode* slow = head;
while (fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow) return true;
}
return false;
}
};
~~~
链表只有一个节点且该节点构成自环：
链表3->4->5->6->7，4->5->6->7形成环：
**四. 小结**
关于有环链表中快慢指针一定会相遇的解决方法，可以简单地证明：
如果有环的话，快慢指针都会进入有环的部分。
而一旦进入有环的部分，一快一慢，学过物理都知道，其实可以相当于一个静止另一个每次移动一格。
到此，为什么一定会相遇应该已经很明显了吧~
该方法广为人知，不知是否有更为精妙的解法？
';