[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;
    }
};