问题描述
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++
/**
* 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) {
ListNode *slow = head;
ListNode *fast = head; while(){
if(!slow)
return NULL;
else
slow = slow->next;
if(!fast->next || !fast->next->next)
return NULL;
else
fast = fast->next->next;
if(slow == fast){
slow = head;
while(slow != fast){
slow = slow -> next;
fast = fast -> next;
}
return slow;
}
}
}
};
未改进