题目链接：Linked List Cycle II

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，初始值都指向头指针，slow每次前进一步，fast每次前进两步。如果存在环，则fast必先进入环，而slow后进入环，两个指针必定相遇（当然，fast先到达尾部为NULL，则为无环链表，返回NULL）。

此时为了寻找环的入口，将slow重新指向表头且仍然每次循环都指向后继，fast每次也指向后继。当fast和slow再次相等时，相等点就是环的入口。证明如下（摘自网络）：

如果fast和slow相遇，那么在相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈（n>=1）。

假设 slow走了s步，则fast走了2s步（fast的步数还等于s加上在环上多转的n圈），设圈的周长为r，则：
    2s = s+nr
    s = nr

               x ____.<-相遇点
                /     \
    ___________/   r   \
         a     \       /
                \_____/

设整个链表长L，起点到环入口点的距离为a，环入口与相遇点距离为x，则
    a+x = s = nr
    a+x = (n-1)r+r = (n-1)r+L-a
    a = (n-1)r+(L-a-x)
其中(L-a-x)为相遇点到环入口点的距离。由此可知，从链表头到环入口点等于(n-1)循环内环加上相遇点到环入口点。于是可以从链表头和相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        if(head == NULL || head -> next == NULL)
            return NULL;
        
        ListNode *s = head, *f = head;
        while(f != NULL && f -> next != NULL)
        {
            s = s -> next;
            f = f -> next -> next;
            
            if(f == s) // 说明有环
            {
                s = head; // 重新指向表头
                while(f != s)
                {
                    s = s -> next; // f每次走1步
                    f = f -> next; // s每次走1步
                }
                return f;
            }
        }
        
        return NULL;
    }
};