-
判斷鏈表有沒有環(huán)
有環(huán)鏈表
一般我們采取快慢指針來判斷鏈表是否有環(huán)拦止。思路主要是：定義兩個指針县遣。
fast和slow；
fast和slow都從head開始往后走汹族。顧名思義艺玲，fast走得快一點(diǎn)，每次走兩步鞠抑；slow走得慢一點(diǎn)，每次走一步忌警；
沒有環(huán)的情況下搁拙，fast肯定率先走到尾結(jié)點(diǎn)；
有環(huán)的情況下法绵，fast先入環(huán)箕速，slow后入環(huán)。因?yàn)?code>fast比slow每次都多走一步朋譬，所以最終在某個地方會相遇（就像跑800m的時候盐茎，A跑得特別快，B跑得特別慢徙赢；A最后在某個地方又追上了B字柠，超了B一圈）。看懂了上面的分析狡赐，應(yīng)該就能寫出相應(yīng)的代碼窑业。
public class 判斷鏈表是否有環(huán) { public boolean isLoop(ListNode head){ ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ return true; } } return false; } } -
有環(huán)的話找到入口結(jié)點(diǎn)
入口結(jié)點(diǎn).png我們要求的是D（入口結(jié)點(diǎn)），現(xiàn)在已知的是I（相遇點(diǎn)枕屉，按照第一題的快慢指針可以求得）常柄。這道題目有點(diǎn)像數(shù)學(xué)題，我們來推導(dǎo)一下：
slow走x步的時候搀擂，fast走了2x步西潘，其中在環(huán)內(nèi)走了x步；
然后我們要知道哨颂，第一次相遇的時候slow還未走完一圈（最多走完一圈）喷市，同樣我們想象兩個人跑800m，A速度是2m/s,B是1m/s咆蒿。A跑完2圈东抹，B跑完1圈的時候兩個人相遇蚂子。這是最極端的情況，即兩個人是從同一個起點(diǎn)開始跑的缭黔。而在本題內(nèi)食茎，一般情況下，fast都會比slow先多走幾步馏谨，這樣fast追上slow所用的時間又會少一點(diǎn)别渔；
那么相遇的時候，slow在環(huán)內(nèi)走了s步惧互，fast在環(huán)內(nèi)走了x+2s步哎媚；
假設(shè)fast已經(jīng)走了n圈。那么有下面的等式：
s=x+2s-nc喊儡，即s=nl-x=(n-1)c+c-x;
我們可以把(n-1)c+c-x理解為拨与，fast先走完(n-1)圈，再走了c-x步艾猜。
由此我們可以知道买喧，在相遇點(diǎn)的時候，我們再走x步就能又回到入口結(jié)點(diǎn)匆赃。那么I到D的距離就是x淤毛，和A到D的距離是一樣的然后是代碼：
public class 環(huán)的入口結(jié)點(diǎn) { public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = pHead; ListNode fast = pHead; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ // 相遇就跳出循環(huán) break; } } if(fast.next == null || fast.next.next == null){ return null; } ListNode p1 = pHead; // 頭結(jié)點(diǎn) ListNode p2 = slow; // 相遇結(jié)點(diǎn) while(p1 != p2){ // 相等的時候即p1、p2同時到達(dá)相遇結(jié)點(diǎn) p1 = p1.next; p2 = p2.next; } return p1; } } -
環(huán)結(jié)點(diǎn)個數(shù)
這個問題在我們會求相遇點(diǎn)后已經(jīng)變得非常簡單算柳。我們讓slow繼續(xù)走走走低淡，又走回到相遇點(diǎn)就代表走完了一圈，就能求得環(huán)長public class 環(huán)結(jié)點(diǎn)個數(shù) { public static int nodeNumOfLoop(ListNode head){ ListNode fast = head; ListNode slow = head; int count = 0; // count計數(shù) while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ break; } } if(fast.next == null || fast.next.next == null){ return 0; } ListNode temp = slow; do{ slow = slow.next; count++; } while(slow != temp); return count; } } -
鏈表長度
看第2題的圖瞬项，總長就=c+x嘛蔗蹋！public class 鏈表長度 { public static int lLength(ListNode head){ ListNode p1 = head; int length = 0; if(meetNode(head) == null){ while(p1 != null){ p1 = p1.next; length++; } return length; }else{ return EntryNodeOfLoop(head)+nodeNumOfLoop(head); } } public static ListNode meetNode(ListNode head){ // 相遇點(diǎn) ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ return slow; } } return null; } public static int EntryNodeOfLoop(ListNode head){ // 環(huán)入口結(jié)點(diǎn)距頭結(jié)點(diǎn)的距離 int count = 0; ListNode p1 = head; ListNode p2 = meetNode(head); while(p1 != p2){ p1 = p1.next; p2 = p2.next; count++; } return count; } public static int nodeNumOfLoop(ListNode head){ // 環(huán)長度（環(huán)結(jié)點(diǎn)個數(shù)） int count = 0; ListNode slow = meetNode(head); ListNode temp = slow; do{ slow = slow.next; count++; } while(slow != temp); return count; } }
總結(jié)一下。
第一個囱淋，判斷是否有環(huán)纸颜。轉(zhuǎn)換成求相遇結(jié)點(diǎn)的問題，用快慢指針解決绎橘。相遇則有環(huán)胁孙，反之無環(huán)。
第二個称鳞，求入口結(jié)點(diǎn)（D）涮较。先求相遇結(jié)點(diǎn)，然后記住一個結(jié)論冈止。頭結(jié)點(diǎn)到入口結(jié)點(diǎn)的距離（x)與相遇結(jié)點(diǎn)到入口結(jié)點(diǎn)的距離相同狂票。
第三個，求環(huán)結(jié)點(diǎn)個數(shù)（c）熙暴。求相遇結(jié)點(diǎn)闺属，然后走一圈慌盯，計數(shù)。
第四個掂器，求鏈表長度亚皂。轉(zhuǎn)換成求相遇結(jié)點(diǎn)+求入口結(jié)點(diǎn)的問題。然后x（根據(jù)入口結(jié)點(diǎn)求得）+c（根據(jù)相遇結(jié)點(diǎn)求得）
不管三七二十一国瓮，相遇結(jié)點(diǎn)總是要求的灭必，從一開始拿到問題，就要判斷成不成環(huán)乃摹，反正要求的禁漓！就連入口結(jié)點(diǎn)也是根據(jù)相遇結(jié)點(diǎn)求的。然后其他問題就是求相遇結(jié)點(diǎn)和入口結(jié)點(diǎn)的變體了孵睬。
