142. 環(huán)形鏈表 II

難度中等2051

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

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

不允許修改?鏈表。

?

示例 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é)點的數(shù)目范圍在范圍?[0, 104]?內(nèi)

• -105?<= Node.val <= 105

• pos?的值為?-1?或者鏈表中的一個有效索引

?

進(jìn)階：你是否可以使用?O(1)?空間解決此題？->雙指針

第一種對法 ：

/**

?*?Definition?for?singly-linked?list.

?*?struct?ListNode?{

?*?????int?val;

?*?????struct?ListNode?*next;

?*?};

?*/

struct?ListNode?*detectCycle(struct?ListNode?*head)?{

????struct?ListNode?*fast?=?head;

????struct?ListNode?*slow?=?head;

????while(fast!=NULL&&fast->next!=NULL){

????????fast=fast->next->next;

????????slow=slow->next;

????????if(fast==slow){

????????????struct?ListNode*?tmp1?=?fast;

????????????struct?ListNode*?tmp2?=?head;

????????????while(tmp1!=tmp2){

????????????????tmp1=tmp1->next;

????????????????tmp2=tmp2->next;

????????????}

????????????return?tmp1;

????????}

????}

????return?NULL;

}

思路：

利用快慢指針來判斷是否有環(huán)和相遇點，在另設(shè)兩個臨時指針來判斷環(huán)開始的地方。從下圖公式推導(dǎo)可知，從鏈表頭到環(huán)開始的地方和從相遇點到環(huán)開始的地方的節(jié)點數(shù)相同，因此當(dāng)在頭結(jié)點處的臨時指針與在相遇點的臨時指針相遇時的結(jié)點就是環(huán)開始的地方。