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?
Solution:
首先选取一快一慢两个指针fast与slow: fast每步走两个结点，slow每步走一个结点。若链表有环，则fast将会在某一个时刻追上slow。
1. 假设链表有环，且链表长度为n，循环从第k + 1个结点开始(亦即走k步进入循环)
2. 让两个指针fast, slow从链表头同时开始遍历链表
3. 这两个指针相遇时应满足：
2 * s1 = s2
s2 - s1 = (n - k) * t
故有：s1 = (n - k) * t，即慢的指针每走n - k步，两个指针会相遇一次。
4. 由3我们知道，快慢指针第一次相遇时，慢的指针走了n - k步，快的指针走了(n - k) * 2步。实际上，慢的指针还有k步到达链表的尾，也就是循环的起点。
此时，我们只需要放把快指针速度变为1，同时将其放在起点，慢指针放在第一次相遇的结点。再次开始运动，这次相遇的结点就是循环的起点，两个指针都走了k步。
/** * 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) { if(head == NULL || head -> next == NULL) return NULL; ListNode *fast = head, *slow = head; while(true) { fast = fast -> next; if(fast == NULL) return NULL; fast = fast -> next ; if(fast == NULL) return NULL; slow = slow -> next; if(fast == slow) { fast = head; while(true) { if(fast == slow) return fast; fast = fast -> next; slow = slow -> next; } } } } };
[LeetCode] Linked List Cycle II,布布扣,bubuko.com
[LeetCode] Linked List Cycle II
原文：http://www.cnblogs.com/changchengxiao/p/3598844.html