1.這是一個(gè)判斷 鏈表中是否有環(huán) 的題目．是昨天那個(gè)題目的衍生要尔，判斷環(huán)在哪個(gè)地方．
鏈接：https://leetcode.com/problems/linked-list-cycle-ii/
題目的意思就是輸入一個(gè)鏈表看峻，然后判斷鏈表是否構(gòu)成了環(huán)狀結(jié)構(gòu)片酝，并且找出環(huán)結(jié)構(gòu)的位置雕擂。
這里有兩個(gè)思路解決這個(gè)問(wèn)題：
**
1.使用鍵值對(duì)绽榛，記錄這個(gè)Node，發(fā)現(xiàn)相同直接返回這個(gè)值就可以了。ps：其實(shí)集合（Set就可以接剩，插入錯(cuò)誤，直接判斷有環(huán)）
2.使用長(zhǎng)短指針的思路萨咳。先判斷是否有環(huán)懊缺，然后根據(jù)相關(guān)信息計(jì)算出環(huán)的位置，下面詳細(xì)解釋培他。**
2.題解：
給出以上兩個(gè)思路的代碼：
思路1：
class Solution:
# 2- 使用字典記錄
def hasCycle(self, head):
dict_list = {}
i = 0
node = head
while node:
if node in dict_list:
return "tail connects to node index " + str(dict_list[node]) # 這里可以直接返回在哪個(gè)節(jié)點(diǎn)形成環(huán)
else:
dict_list[node] = i # 記錄鍵值對(duì)
i += 1
node = node.next
return "no cycle"
思路3：
詳細(xì)解釋：
1.首先通過(guò)長(zhǎng)短指針判斷是否有環(huán)鹃两，如果有的執(zhí)行下一步，沒(méi)有的話舀凛，返回“no cycle”
2.假設(shè) 到入口的距離是H俊扳，環(huán)的長(zhǎng)度是C，第一次相遇的位置是D猛遍。
因此馋记，慢指針的距離是
dis_slow = H+mC+D，m為自然數(shù)
快指針的距離是
dis_fast = H+nC+D懊烤，m為自然數(shù)
因?yàn)榭熘羔樳\(yùn)動(dòng)的步長(zhǎng)是慢指針的兩倍抗果，因此，得到以下的這個(gè)公式奸晴。
2*dis_slow = dis_fast
H = (n-2m)C - D
將n-2m用k代替
H =kC - D
3.讓慢指針回到head節(jié)點(diǎn)冤馏，和fast同時(shí)以步長(zhǎng)為1的速度跑。此時(shí)寄啼，等他們兩相遇時(shí)候逮光，慢節(jié)點(diǎn)運(yùn)動(dòng)H，快節(jié)點(diǎn)運(yùn)動(dòng)KC-D的長(zhǎng)度墩划。此時(shí)返回H節(jié)點(diǎn)位置即可涕刚。
畫(huà)圖解釋：
# 3- 使用長(zhǎng)短指針記錄
def hasCycle(self, head):
# 1.判斷是否有環(huán)
try:
fast = head.next.next
slow = head.next
while slow != fast:
slow = slow.next
fast = fast.next.next
except:
return "no cycle"
# 2 根據(jù)公式計(jì)算出對(duì)應(yīng)的環(huán)開(kāi)始的位置
slow = head
i = 0
while slow is not fast:
slow, fast = slow.next, fast.next
i += 1
return "tail connects to node index " + str(i)
不過(guò)這一題，有個(gè)坑乙帮，這個(gè)不是直接返回字符串杜漠，而是返回，Ｎone或者節(jié)點(diǎn)．
3.完整代碼
查看鏈接：
https://github.com/Wind0ranger/LeetcodeLearn/edit/master/1-List/142-Linked-List-Cycle-II.py
