漫畫算法：如何判斷鏈表有環(huán)孕荠？ - 文章 - 伯樂在線
大四畢業(yè)前夕预厌，計算機(jī)學(xué)院阿迈，
正在四處求職的小灰碰到了同系的學(xué)霸大黃……
小灰邊說邊回憶著上周去面試的情形……
有一個單向鏈表，鏈表當(dāng)中有可能出現(xiàn)“環(huán)”轧叽，就像下圖這樣苗沧。如何用程序判斷出這個鏈表是有環(huán)鏈表？
方法一：首先從頭節(jié)點開始炭晒，依次遍歷單鏈表的每一個節(jié)點待逞。每遍歷到一個新節(jié)點，就從頭節(jié)點重新遍歷新節(jié)點之前的所有節(jié)點网严，用新節(jié)點ID和此節(jié)點之前所有節(jié)點ID依次作比較识樱。如果發(fā)現(xiàn)新節(jié)點之前的所有節(jié)點當(dāng)中存在相同節(jié)點ID，則說明該節(jié)點被遍歷過兩次震束，鏈表有環(huán)怜庸；如果之前的所有節(jié)點當(dāng)中不存在相同的節(jié)點，就繼續(xù)遍歷下一個新節(jié)點垢村，繼續(xù)重復(fù)剛才的操作割疾。
例如這樣的鏈表：A->B->C->D->B->C->D， 當(dāng)遍歷到節(jié)點D的時候嘉栓，我們需要比較的是之前的節(jié)點A宏榕、B、C侵佃，不存在相同節(jié)點麻昼。這時候要遍歷的下一個新節(jié)點是B，B之前的節(jié)點A趣钱、B涌献、C、D中恰好也存在B首有，因此B出現(xiàn)了兩次燕垃，判斷出鏈表有環(huán)枢劝。
假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S卜壕。那么算法的時間復(fù)雜度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 您旁， 可以簡單地理解成 O(N*N)。而此算法沒有創(chuàng)建額外存儲空間轴捎，空間復(fù)雜度可以簡單地理解成為O(1)鹤盒。
方法二：首先創(chuàng)建一個以節(jié)點ID為鍵的HashSet集合，用來存儲曾經(jīng)遍歷過的節(jié)點侦副。然后同樣是從頭節(jié)點開始侦锯，依次遍歷單鏈表的每一個節(jié)點。每遍歷到一個新節(jié)點秦驯，就用新節(jié)點和HashSet集合當(dāng)中存儲的節(jié)點作比較尺碰，如果發(fā)現(xiàn)HashSet當(dāng)中存在相同節(jié)點ID，則說明鏈表有環(huán)译隘，如果HashSet當(dāng)中不存在相同的節(jié)點ID亲桥，就把這個新節(jié)點ID存入HashSet，之后進(jìn)入下一節(jié)點固耘，繼續(xù)重復(fù)剛才的操作题篷。
這個方法在流程上和方法一類似，本質(zhì)的區(qū)別是使用了HashSet作為額外的緩存厅目。
假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是D番枚，鏈表的環(huán)長是S。而每一次HashSet查找元素的時間復(fù)雜度是O(1), 所以總體的時間復(fù)雜度是1*(D+S)=D+S璧瞬，可以簡單理解為O(N)户辫。而算法的空間復(fù)雜度還是D+S-1，可以簡單地理解成O(N)嗤锉。
等通知就是沒通知渔欢，這是職場上公認(rèn)的語言。
以上就是小灰悲劇的回憶……
方法三：首先創(chuàng)建兩個指針1和2（在java里就是兩個對象引用）瘟忱，同時指向這個鏈表的頭節(jié)點奥额。然后開始一個大循環(huán)，在循環(huán)體中访诱，讓指針1每次向下移動一個節(jié)點垫挨，讓指針2每次向下移動兩個節(jié)點，然后比較兩個指針指向的節(jié)點是否相同触菜。如果相同九榔，則判斷出鏈表有環(huán)，如果不同，則繼續(xù)下一次循環(huán)哲泊。
例如鏈表A->B->C->D->B->C->D剩蟀，兩個指針最初都指向節(jié)點A，進(jìn)入第一輪循環(huán)切威，指針1移動到了節(jié)點B育特，指針2移動到了C。第二輪循環(huán)先朦，指針1移動到了節(jié)點C缰冤，指針2移動到了節(jié)點B。第三輪循環(huán)喳魏，指針1移動到了節(jié)點D棉浸，指針2移動到了節(jié)點D，此時兩指針指向同一節(jié)點刺彩，判斷出鏈表有環(huán)涮拗。
此方法也可以用一個更生動的例子來形容：在一個環(huán)形跑道上，兩個運動員在同一地點起跑迂苛，一個運動員速度快，一個運動員速度慢鼓择。當(dāng)兩人跑了一段時間三幻，速度快的運動員必然會從速度慢的運動員身后再次追上并超過，原因很簡單呐能，因為跑道是環(huán)形的念搬。
假設(shè)從鏈表頭節(jié)點到入環(huán)點的距離是D，鏈表的環(huán)長是S摆出。那么循環(huán)會進(jìn)行S*K次朗徊，K為正整數(shù)（為什么是S*K次，有心的同學(xué)可以自己揣摩下）偎漫，可以簡單理解為O（N）爷恳。除了兩個指針以外，沒有使用任何額外存儲空間象踊，所以空間復(fù)雜度是O（1）温亲。
問題一：判斷兩個單向鏈表是否相交，如果相交杯矩，求出交點栈虚。
問題二：在一個有環(huán)鏈表中，如何找出鏈表的入環(huán)點史隆？
