算法
此题思路很巧妙——快慢指针
1. fast速度2,slow速度1,直到第一次相遇
2. slow回到起点,fast不动
3. fast和slow速度1运动,再次相遇时的位置一定是成环的位置
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) {
// use fast and slow points
auto fast = head, slow = head;
while(fast) {
fast = fast->next;
slow = slow->next;
if (fast != NULL) fast = fast->next;
else break;
if (fast == slow) {
slow = head;
while(fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast; // second time meet position
}
}
return NULL;
}
};