首先判斷是否存在環(huán)粥帚,如果是把slow移動到頭結點,開始和fast同步向后移動限次,如果相等就返回芒涡。
注意對于最后slow == fast的判斷,需要放在循環(huán)入口處卖漫,否則對于如下case失效:
if(slow == fast)
return fast;
[1,2]
tail connects to node index 0
第一次檢查cycle時候 fast == slow == 1
接下來循環(huán)入口如果不判斷费尽,之后兩個會在[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;
}
}