可知首先要判断是否有环,然后给出目标的位置。
slow指针走一步,fast指针走两步。当这两个指针都进入环时,fast指针相当于slow指针只走了一步,因此肯定两者会相遇。
但这只是相遇点,不是环起始点,但根据计算可知,此时都以同样的单位速度时,再相遇时就可以得到相交点。
点击查看代码
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode*dummy=new ListNode(0);
dummy->next=head;
ListNode*slow=dummy;ListNode*fast=dummy;
if(!head||!head->next){return NULL;}
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
slow=dummy;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
}
return NULL;
}
};