題干
141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
給予一個鏈表，返回這個鏈表是否存在循環(huán)。
142. 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.
給予一個鏈表，返回這個鏈表從哪個節(jié)點開始循環(huán)俐镐，如果鏈表中沒有循環(huán)，則返回null彭雾。
解題思路
鏈表存在循環(huán)抄沮，指的是鏈表中某一個節(jié)點的next指針指向了過去的一個節(jié)點。
那么我們?nèi)绾蝸砼袛嘁粋€鏈表是否存在循環(huán)呢粥庄？
比較蠢的一個辦法丧失，判斷一個節(jié)點是否有出現(xiàn)過。
不能單獨靠val來判斷節(jié)點是否出現(xiàn)惜互，因為題干里沒有說所有的val都是unique的布讹。
但是每個節(jié)點的指針是獨特的，只要把遍歷過的指針存到一個數(shù)組中训堆，如果某個指針出現(xiàn)了第二次描验，那說明這個數(shù)組就是重復(fù)的。
但是吧坑鱼，這樣就太不優(yōu)雅了膘流，我們有沒有什么辦法不利用額外的空間來完成這個問題呢？
答案是有的：快慢指針鲁沥。
我們可以設(shè)計兩個游標(biāo)指針呼股，步長并不相同，如果兩者正好能指向同一個節(jié)點画恰，那么就說明鏈表中存在循環(huán)彭谁。
var hasCycle = function(head) {
if(head==null){
return false;
}
let slow = head;
let fast = head;
while(true){
slow = slow.next;
if(!fast||!fast.next){
return false;
}
fast = fast.next.next;
if(slow==fast){
return true;
}
}
return true;
};
這樣第一題就解決了，第二題還遠(yuǎn)嗎允扇？
在第一題中我們設(shè)慢指針步長為1缠局，快指針步長為2则奥，這個時候當(dāng)經(jīng)過多少步后，指針會指向同一個節(jié)點呢甩鳄？
做一個簡單的數(shù)學(xué)算式逞度，設(shè)鏈表不參加循環(huán)的長度為a，鏈表循環(huán)部分長度為b妙啃，步數(shù)為x档泽。
那么可以推得：x+b = 2x
經(jīng)過的步數(shù)就等于慢指針走過的步數(shù)，這里我們可以推出循環(huán)部分的鏈表的長度揖赴，知道了這個長度以后馆匿，我們可以再設(shè)計一對快慢指針，這次兩個指針步長相同燥滑，但是快指針會先走出b步渐北，這樣當(dāng)快指針走到鏈表末尾時，慢指針正好指向了非循環(huán)部分的最后一個節(jié)點铭拧。而兩個指針各再向前一步赃蛛，得到的則是循環(huán)開始的節(jié)點。
而在剛才的程序中搀菩，慢指針正好是那個已經(jīng)走出了b步的指針呕臂，我們只需要將快指針指向頭節(jié)點，然后循環(huán)步長為1即可肪跋。
而對于不存在循環(huán)的鏈表來說歧蒋，將上題中的return false的部分改為return null即可。
var detectCycle = function(head) {
if(head==null){
return false;
}
let slow = head;
let fast = head;
while(slow!=fast){
slow = slow.next;
if(!fast||!fast.next){
return null;
}
fast = fast.next.next;
}
fast = head;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return slow;
};
