141. Linked List Cycle&142. Linked List Cycle II（剑指Offer-链表中环的入口节点）

题目：

141.Given a linked list, determine if it has a cycle in it.

142.Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

思路：

　　带环链表如图所示。设置一个快指针和一个慢指针，快指针一次走两步，慢指针一次走一步。快指针先进入环，慢指针后进入环。在进入环后，可以理解为快指针追赶慢指针，由于两个指针速度相差1，则最终会相遇。

　　当快指针和慢指针相遇时，证明链表中存在环。141可解。

　　假设两个指针在C点相遇，此时慢指针走过的路程为AB+BC，快指针走过的路程为AB+BC+CB+BC。由于时间相同，快指针的速度为慢指针的2倍，则快指针走过的路程为慢指针的2倍。因此，2*（AB+BC）=AB+BC+CB+BC，得到AB=CB。

　　由此可以得到两个结论：

环的长度即为AB+BC，即A到C的长度。
当快指针和慢指针相遇后，把快指针放置于A点（即链表头部），慢指针仍在C点。此时两个指针一次走一步，相遇的节点即为环的起点。142可解。

代码：

141. Linked List Cycle

 1 struct ListNode {
 2     int val;
 3     ListNode *next;
 4     ListNode(int x) :
 5             val(x), next(NULL) {
 6     }
 7 };
 8 class Solution {
 9 public:
10     bool hasCycle(ListNode *head) {
11         ListNode *fast = head;
12         ListNode *slow = head;
13         while ((fast != NULL) && (slow != NULL) && (fast->next != NULL)) {
14             fast = fast->next->next;
15             slow = slow->next;
16             if (fast == slow) {
17                 return true;
18             }
19         }
20         return false;
21     }
22 };

View Code

142. Linked List Cycle II

 1 struct ListNode {
 2     int val;
 3     ListNode *next;
 4     ListNode(int x) :
 5             val(x), next(NULL) {
 6     }
 7 };
 8 class Solution {
 9 public:
10     ListNode *detectCycle(ListNode *head) {
11         ListNode *fast = head;
12         ListNode *slow = head;
13         while ((fast != NULL) && (slow != NULL) && (fast->next != NULL)) {
14             fast = fast->next->next;
15             slow = slow->next;
16             if (fast == slow) {
17                 fast = head;
18                 while (fast != slow) {
19                     fast = fast->next;
20                     slow = slow->next;
21                 }
22                 return fast;
23             }
24         }
25         return NULL;
26     }
27 };

View Code