142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:
Can you solve it without using extra space?

---

本题在LeetCode Linked List Cycle的基础上更进一步，需要求出链表中环的起点位置。 接上一题，相遇位置在Z，此时如果令slower=head，然后slower和faster都以相同的速度走a步，则slower刚好能到环的起点位置Y，那么faster会在哪里呢。 上一题推出来相遇的时候有：a+b=(n-2m)c，如果faster在相遇点走a步，则相当于走了a=(n-2m)c-b，(n-2m)c相当于绕圈n-2m次，(n-2m)c-b的意思就是在z点绕圈n-2m次的基础上，退回b步，看图，退回b步正好到达了环的起点Y。 所以快慢指针再走a步之后，正好在环的起点相遇了！ 于是本题的思路就是：先用上一题的方法找到相遇位置，然后slower回到head节点，slower和faster都再次单步走，再次相遇时，就是环的起点。 完整代码如下：

class Solution {
public:
    ListNode* detectCycle(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
            if (faster == slower)
                break;
        }
        if (faster->next == NULL || faster->next->next == NULL)
            return NULL;
        slower = head;
        while (slower != faster) {
            slower = slower->next;
            faster = faster->next;
        }
        return slower;
    }
};

本代码提交AC，用时13MS。