LeetCode: 142. Linked List Cycle II
题目描述
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up: Can you solve it without using extra space?
解题思路
利用 LeetCode: 141. Linked List Cycle 题解 的快慢指针找到距离起点 n 个周期的节点（设慢指针移动 a+b 各节点， 则快指针移动 a+b+nT， 而快指针速度是慢指针的二倍，因此 2(a+b)=a+b+nT， 即 a+b = nT， 即快慢指针相遇的节点距离起始节点 nT（n 个周期）），然后一个指针从起始节点出发，另一个指针距离起始位置 nT 个节点出发， 大部分慢指针移动 a 个节点后， 快指针移动 a + nT 个节点， 此时相遇于环的起始节点。
AC 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *
detectCycle(ListNode *head) {
ListNode* pFast = head, *pSlow = head;
do
{
if(pFast != nullptr) pFast = pFast->next;
if(pFast != nullptr) pFast = pFast->next;
if(pSlow != nullptr) pSlow = pSlow->next;
}
while(pFast != nullptr && pSlow != nullptr && pFast != pSlow);
if(pFast == nullptr)
return nullptr;
pSlow = head;
while(pSlow != pFast)
{
pFast = pFast->next;
pSlow = pSlow->next;
}
return pFast;
}
};
