单链表,问有没有环,若有,找到环的入口.
Lintcode上挑战,只许使用常数的空间.
设一个快指针fast,一个慢指针slow,fast每次走2步,slow每次走1步.
若无相遇找到了链尾,则无环,若相遇了,则有环.
设从链头到环入口点走了a步,从环入口到相遇点走了x步,环长r.相遇时,slow走了s步,fast走了2s步.
有:
s=a+x, 2s=a+nr+x.
所以a+x=nr->a=nr-x.
注意理解a=nr-x.意思是从链头走到环入口的 步数=再走n圈,并退x步.那刚好也在环入口.
1 class Solution { 2 public: 3 ListNode *detectCycle(ListNode *head) { 4 ListNode *slow = head, *fast = head; 5 while (fast && fast->next) { 6 slow = slow->next; 7 fast = fast->next->next; 8 if (slow == fast) 9 break; 10 } 11 if (!fast || !fast->next) 12 return NULL; 13 slow = head; 14 while (slow != fast) { 15 slow = slow->next; 16 fast = fast->next; 17 } 18 return slow; 19 } 20 };
原文：http://www.cnblogs.com/yujinding/p/7027739.html