[LeetCode] 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

问题描述：给定一个链表，返回环开始的节点，如果没有环，就返回NULL。

这道题是前面一道题的扩展，前面一题是判断链表中是否有环，这道题是，如果有环的话，找到环开始的那个节点。

用两个指针(fast和slow)遍历链表，采用前面一题的方法，当fast和slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈，如果slow走了s步，那么fast走了2s步，设环长为r，那么：

2s = s + nr => s = nr

设整个链表长为L，入口环与相遇点距离为x，起点到入口点的距离为a：

a + x = nr => a + x = (n - 1)r + r = (n - 1)r + L - a => a = (n - 1)r + (L - a - x)

其中，(L - a - x)是沿链表的方向，相遇点到环入口的距离，因此，从链表头到环入口点等于(n - 1)个内循环 + 相遇点到环入口的距离。

于是：从链表头和相遇点各设置一个指针，步长为1，两个指针必定相遇，且相遇第一点为环入口：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return NULL;
        ListNode *fast = head, *slow = head;

		while(fast && fast->next) {
			slow = slow->next;
			fast = fast->next->next;
			if(slow == fast) {
				break;
			}
		}
		if(slow != fast)
		    return NULL;
		slow = head;
		while(slow != fast) {
		    slow = slow->next;
		    fast = fast->next;
		}
		return slow;
    }
};