給一個(gè)鏈表惭缰，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)笼才，否則漱受，輸出null。
分析：如何判斷有環(huán)骡送？如何找到環(huán)的入口節(jié)點(diǎn)昂羡？
首先判斷是否有環(huán)
1.窮舉法。（每個(gè)節(jié)點(diǎn)都放到一個(gè)哈希表數(shù)組）這里我們使用容器set摔踱，如果遍歷到某個(gè)鏈表結(jié)點(diǎn)已經(jīng)在set中虐先，那么該點(diǎn)即為環(huán)的入口結(jié)點(diǎn)；
2.快慢指針?lè)ā?br>
（1）快指針一次走兩步派敷，慢指針一次走一步蛹批。如果有環(huán)的話，那么快指針一定會(huì)追上快指針膀息，就像一個(gè)環(huán)形的跑道中般眉，跑的快的運(yùn)動(dòng)員一定會(huì)追上跑的慢的運(yùn)動(dòng)員。
（2）快指針先走一步潜支，然后和慢指針一起從從節(jié)點(diǎn)開始走甸赃。如果有環(huán)的話，那么快指針一定會(huì)追上快指針冗酿，就像一個(gè)環(huán)形的跑道中埠对，跑的快的運(yùn)動(dòng)員一定會(huì)追上跑的慢的運(yùn)動(dòng)員。
如何找到環(huán)的入口節(jié)點(diǎn)
參考一種思路裁替。一個(gè)數(shù)學(xué)問(wèn)題项玛。
如上圖，
首先我們?cè)O(shè)：
鏈表頭到環(huán)入口長(zhǎng)度為--a
環(huán)入口到相遇點(diǎn)長(zhǎng)度為--b
相遇點(diǎn)到環(huán)入口長(zhǎng)度為--c
先說(shuō)說(shuō)快慢指針?lè)ǖ模?）弱判。
如果鏈表存在環(huán)襟沮，那么計(jì)算出環(huán)的長(zhǎng)度n，快指針先走n步昌腰，然后快指針和慢指針一塊走开伏，當(dāng)兩者相遇時(shí)，即為環(huán)的入口處遭商；
證明如下：
設(shè)：
鏈表頭到環(huán)入口長(zhǎng)度為--a
鏈表總長(zhǎng)度--k
環(huán)的長(zhǎng)度--n
則：a+n=k,當(dāng)快節(jié)點(diǎn)先走了一個(gè)環(huán)的長(zhǎng)度n時(shí)固灵，再走一個(gè)a的路程就到達(dá)鏈表的終點(diǎn)，也就是環(huán)的入口劫流。所以此時(shí)讓一個(gè)指針從頭節(jié)點(diǎn)開始走巫玻，當(dāng)兩個(gè)指針相遇時(shí)丛忆，即為環(huán)的入口節(jié)點(diǎn)。
快慢指針?lè)ǖ模?）
兩個(gè)結(jié)論：
1仍秤、設(shè)置快慢指針熄诡，假如有環(huán)，他們最后一定相遇徒扶。
2粮彤、兩個(gè)指針?lè)謩e從鏈表頭和相遇點(diǎn)繼續(xù)出發(fā)根穷，每次走一步姜骡，最后一定相遇與環(huán)入口。
證明如下
證明1：設(shè)置快慢指針fast和low屿良，fast每次走兩步圈澈，low每次走一步。假如有環(huán)尘惧，兩者一定會(huì)相遇（因?yàn)閘ow一旦進(jìn)環(huán)康栈，可看作fast在后面追趕low的過(guò)程寂殉，每次兩者都接近一步宣增，最后一定能追上）勉盅。
證明2：
快指針路程=a+(b+c)k+b 坎背，k>=1 其中b+c為環(huán)的長(zhǎng)度柬焕，k為繞環(huán)的圈數(shù)（k>=1,即最少一圈欣硼，不能是0圈骑冗，不然和慢指針走的一樣長(zhǎng)秉宿，矛盾）疙剑。
慢指針路程=a+b
快指針走的路程是慢指針的兩倍氯迂，所以：
（a+b）*2=a+(b+c)k+b
化簡(jiǎn)可得：
a=(k-1)(b+c)+c 這個(gè)式子的意思是： 鏈表頭到環(huán)入口的距離=相遇點(diǎn)到環(huán)入口的距離+（k-1）圈環(huán)長(zhǎng)度。其中k>=1,所以k-1>=0圈言缤。所以兩個(gè)指針?lè)謩e從鏈表頭和相遇點(diǎn)出發(fā)嚼蚀，最后一定相遇于環(huán)入口。
通過(guò)的測(cè)試用例
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode fast=pHead;
ListNode slow=pHead;
ListNode meet=null;
while(fast.next!=null||fast==null){
fast=fast.next.next;
slow=slow.next;
if(slow==fast){
meet=fast;
fast=pHead;
while(fast!=meet){ //判斷節(jié)點(diǎn)相遇
fast=fast.next;
meet=meet.next;
}
return fast;
}
}
if(fast.next==null||fast==null){
return null;
}
return null;
}
}
ps:題外話:昨天去孩子王筆試+面試 這是面試官問(wèn)我的一道題目：如何在一個(gè)單鏈表判斷是否有環(huán)管挟，很遺憾轿曙，在面試官提示快慢指針的情況下還是沒(méi)有想清楚，回答錯(cuò)誤僻孝。希望吸取教訓(xùn)导帝，好好補(bǔ)基礎(chǔ)+多想想。2019/5/21
