给定一个链表头, 探测其是否有环, 如果没有返回NULL, 如果有返回环开始的位置.

环开始的位置定义为被两个指针指向的位置.

算法描述:

1. 快慢指针遍历, 如果到头说明无环返回NULL, 如果相遇说明有环, 进入2.

2. 慢指针回到起点, 快慢指针每次移动一格直到相遇, 返回快指针/慢指针.

代码:

 1 class Solution { 2 public: 3     ListNode *detectCycle(ListNode *head) { 4         if (!head || !head->next) return NULL; 5         ListNode *fast = head; 6         ListNode *slow = head; 7         while (true) { 8             if (!fast || !fast->next) return NULL; // no cycle 9             slow = slow->next;10             fast = fast->next->next;11             if (slow == fast) break; // has cycle12         }13         slow = head;14         while (slow != fast) {15             slow = slow->next;16             fast = fast->next;17         }18         return slow;19     }20 };

 证明: (仅证明有环情况)

我们设非环部分长为D, 环长为C, 快慢指针相遇时慢指针走过的弧长为L

1. 当快慢指针相遇时, 慢指针行进的距离为: D + L

　　　　　　　　　　　快指针行进的距离为: D + L + n * C

　　　　　　　　　　　由快慢指针性质可以得到: 2(D + L) = D + L + n * C

　　　　　　　　　　　　　　　　　　　　　　　　D + L = n * C

　　　　　　　　　　　　　　　　　　　　　　　　D = n * C - L

　　　　　　　　　　　　　　　　　所以, 慢指针: n * C

　　　　　　　　　　　　　　　　　　　　快指针: 2 * n * C

2. 把慢指针放回起点, 当慢指针到达环的起点时,

慢指针行进的距离为: D　　　　　　　　　　　　　　　　　　　　　　  

快指针行进的距离为: 2 * n * C + n * C - L

　　　　　　　　　　= 3 * n * C - L

　　　　　　　　　　= 3 * (n-1) * C + (C - L)

即快指针也正好走完剩余的弧长. 到达起点. 证毕.