[LeetCode系列]链表环探测问题II

给定一个链表头, 探测其是否有环, 如果没有返回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 cycle
12         }
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)

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