題目鏈接：142.環(huán)形鏈表II

題目描述：

????????給定一個鏈表的頭節(jié)點 ?head?，返回鏈表開始入環(huán)的第一個節(jié)點。?如果鏈表無環(huán)，則返回?null。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤?next?指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環(huán)。注意：pos?不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改?鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例?2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

提示：

• 鏈表中節(jié)點的數目范圍在范圍?[0, 104]?內
• -105 <= Node.val <= 105
• pos?的值為?-1?或者鏈表中的一個有效索引

思路：參考環(huán)形鏈表I?，依舊使用快慢指針解決

????????參考環(huán)形鏈表I?，快慢指針一定會在環(huán)形鏈表中相遇。

? ? ? ? 以示例1為例：

? ? ? ? head為鏈表的頭結點，meet為快慢指針在環(huán)中的相遇點，?由圖可以初步判斷：

????????meet到入環(huán)的初始結點的距離等于head到入環(huán)的初始結點的距離。

證明：相遇點到入環(huán)起始結點的距離 = 鏈表頭結點到入環(huán)起始結點的距離

? ? ? ? L為頭結點到入環(huán)初始結點的距離，E為入環(huán)的初始結點，M為快慢指針相遇結點，X入環(huán)的初始結點到相遇點的距離，R為環(huán)的周長，R-X為相遇點到頭結點的距離。

? ? ? ? 在快慢指針相遇時，fast所走的路程為L+X+nR，slow所走的路程為L+X

? ? ? ? 又因為慢指針走一步，快指針走兩步，有以下公式：

2*慢指針的路程 = 快指針的路程

? ? ? ? 代入快慢指針路程可以得到：

? ? ?L = (n-1)R+(R-X)，n = 1，2，3...? ? ? ? ? ?

? ? ? ? 當n等于1時，即相遇時，快指針剛好繞環(huán)一圈，則L = R-X?

故相遇點到入環(huán)起始結點的距離 = 鏈表頭結點到入環(huán)起始結點的距離

?代碼實現(xiàn)：

    ListNode* slow = head;ListNode* fast = head;ListNode* meet = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){meet = slow;break;}}

? ? ? ? 定義快慢指針，找到相遇結點meet，找到后跳出循環(huán)。

    ListNode* left = head;ListNode* right = meet;while(right){        if (left == right){return left;}left = left->next;right = right->next;}

? ? ? ? 找到相遇點后，讓頭結點和相遇點同時往后遍歷，找到入環(huán)的起始結點，若相遇點為空，直接返回NULL。

完整代碼：

 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* slow = head;ListNode* fast = head;ListNode* meet = NULL;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){meet = slow;break;}}ListNode* left = head;ListNode* right = meet;while(right){        if (left == right){return left;}left = left->next;right = right->next;}return NULL;
}