LEET code-- Linked List Cycle II

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

這題很奸詐阿
沒寫過當場要想出來我覺得太難了
硬幹 不好
要先利用再 linked list cycle I的觀念找出是哪一點(meeting)有發現循環
利用meeting指標 跟temp指標來找出head在哪
因為兩個會同時到達cycle head
解釋如下

head: list head
E: the head of the cycle
X: the meeting point of the fast and slow pointer in the Linked list cycle I  
H: distance from head to cycle entry E (head到E的長度) D: distance from E to X (E到X的長度) L: cycle length (cycle的長度) _____ / \ head_____H______E \ \ / X_____/ 因為fast and slow會同時到達X點
對slow而言 他走了 H+D這麼長才到X點
對fast而言 他走了 2(H+D)的長度才跟slow碰面
但是!!!
fast 可能已經走了好幾圈了，可能已經繞了n圈
所以他而外多走了n*L這些距離
所以會變成 H+D+n*L=2(H+D)
H = (n-1)*L + (L-D)
你會發現 H的長度會跟L-D的距離一樣
所以我們可以利用X的指標，讓他跟另外一個從head開始走的指標一起比較
兩個同時都往下走，因為走的距離一樣，當發現兩個指到同一個東西的時候就會剛好是E

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode * hasCycle(struct ListNode *head) { if(head==NULL)return NULL; struct ListNode * fast=head; struct ListNode * slow=head; while(fast && fast->next && fast->next->next){ fast=fast->next->next; slow=slow->next; if(fast == slow)return slow; } if(fast->next == NULL || fast->next->next==NULL)return NULL; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode * meeting=NULL; struct ListNode * temp=head; meeting = hasCycle(head); if(meeting == NULL)return NULL; while(temp && temp->next){ if(temp == meeting)return temp; meeting=meeting->next; temp=temp->next; } }