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

難度中等2042收藏分享切換為英文接收動態(tài)反饋

給定一個鏈表的頭節(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)。

用快慢指針判斷是否有環(huán)；

再用一個從起點開始的新指針q和從節(jié)點B開始的慢指針p同步走，相遇的地方必然是入環(huán)的第一個節(jié)點A。