Linked List Cycle 2
最后更新于：2022-04-01 22:55:56
**一. 题目描述**
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up: Can you solve it without using extra space?
**二. 题目分析**
在Linked List Cycle题目中，使用了两个指针fast与slow检查链表是否有环，该题在此基础上，要求给出链表中环的入口位置，同样需要注意空间复杂度。为了方便解释，以下给出一个有环链表：
其中，设链表头节点到环入口处的距离为`X`，环长度为`Y`，使用`fast`和`slow`两个指针，`fast`指针一次前进两步，`slow`指针一次前进一步，则他们最终会在环中的`K`节点处相遇，设此时`fast`指针已经在环中走过了`m`圈，`slow`指针在环中走过`n`圈，则有：
`fast`所走的路程：`2*t = X+m*Y+K`
`slow`所走的路程：`t = X+n*Y+K`
由这两个方程可得到：
`2X + 2n*Y + 2K = X + m*Y + K`
进一步得到： `X+K = (m-2n)Y`
**从`X+K = (m-2n)Y` 可发现，X的长度加上K的长度等于环长度Y的整数倍！**因此可得到一个结论，即当`fast`与`slow`相遇时，可使用第三个指针`ListNode* cycleStart = head;`，从链表头节点往前走，`slow`指针也继续往前走，直到`slow`与`cycleStart`相遇，该位置就是链表中环的入口处。
**三. 示例代码**
~~~
#include
using namespace std;
struct ListNode
{
int value;
ListNode* next;
ListNode(int x) :value(x), next(NULL){}
};
class Solution
{
public:
ListNode *detectCycle(ListNode *head)
{
if (head == NULL || head->next == NULL || head->next->next == NULL)
return head;
ListNode* fast = head;
ListNode* slow = head;
while (fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
ListNode* cycleStart = head;
while (slow != cycleStart)
{
slow = slow->next;
cycleStart = cycleStart->next;
}
return cycleStart;
}
}
return NULL;
}
};
~~~
一个有环链表，环从第二个节点开始：
**四. 小结**
解答与链表有关的题目时，要多画图，找规律，否则容易遇到各种边界问题。
';