Q3: 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?

解决原理

以不同的速度去遍历链表，slow指针速度是每步一个结点，fast指针速度是每步两个结点

slow遍历节点数是m，fast遍历节点数是2m

假设链表带环，则slow指针与fast指针一定相遇，因为两指针的相对速度是每步一个节点

假设环的长度是L，则当相遇时，fast遍历的节点数比slow遍历的节点数多NL个，N为正整数

2m = m + NL ——> m = NL，m是环长度的整数倍

相遇时的节点位置与起始点相距m个节点，即相距环长度的整数倍

这样如果令slow指针指向链表起始点，fast指针仍然指向相遇点，并且让slow指针与fast指针以相同的速度遍历链表

则当slow指针指向环的起始点时，因为fast与slow的相对距离是NL，则此时fast必定也指向环的起始位置

所以，当两指针指向同一节点时，此节点即为环的起始点

代码C++

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *detectCycle(ListNode *head) {
12         ListNode *slow = head;
13         ListNode *fast = head;
14         
15         while(1){
16             if(!slow) 
17                 return NULL;
18             else 
19                 slow = slow->next;
20             if(!fast->next || !fast->next->next)
21                 return NULL;
22             else 
23                 fast = fast->next->next;
24             if(slow == fast){
25                 slow = head;
26                 while(slow != fast){
27                     slow = slow -> next;
28                     fast = fast -> next;
29                 }
30                 return slow;
31             }
32         }
33     }
34 };

未改进