首先判断是否存在环,如果是把slow移动到头结点,开始和fast同步向后移动,如果相等就返回。
注意对于最后slow == fast的判断,需要放在循环入口处,否则对于如下case失效:
if(slow == fast)
return fast;
[1,2]
tail connects to node index 0
第一次检查cycle时候 fast == slow == 1
接下来循环入口如果不判断,之后两个会在[2]判断相等并返回[2]作为cycle的头结点,明显是不对的。
struct ListNode *detectCycle(struct ListNode *head) {
if(head == NULL)
return NULL;
struct ListNode *slow , *fast;
fast = slow = head;
while(fast){
fast = fast->next;
if(fast){
fast= fast->next;
slow = slow->next;
}
if(slow == fast){
printf("have cycle\n");
break;
}
}
if(fast == NULL)
return NULL;
slow = head;
while(1){
if(slow == fast)
return fast;
slow = slow->next;
fast = fast->next;
}
}