02
06/2015
[LeetCode] Linked List Cycle II
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?
解题思路：
1、解法1，用set来存储所有已经出现的指针，若出现相同的，这就是环开始的点。比较简单，比再赘述。
2、解法2，双指针法。其中一个指针每次走一步，另一个指针每次走两步。若有环，这两个指针肯定会相遇。当相遇时，其中一个指针又从头开始，另一个指针从相遇的地方开始，两个指针每次都走一步。这两个指针肯定会在环入口相遇。数学上的证明见：http://blog.csdn.net/kangrydotnet/article/details/45154927
/**
* 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* one=head;
ListNode* two=head;
while(two!=NULL && two->next!=NULL){
one=one->next;
two=two->next->next;
if(one==two){
break;
}
}
if(two==NULL || two->next==NULL){
return NULL;
}
one = head;
while(two!=one){
one=one->next;
two=two->next;
}
return two;
}
};转载请注明：康瑞部落 » [LeetCode] Linked List Cycle II
0 条评论