題目描述

給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null。

思路

首先要確定這個鏈表中包含環。

然后找到環的長度，根據環的長度找到環的入口節點。

先上結論，然后再證明：

• 結論1：設置快慢指針，快指針每次走一步，慢指針每次走兩步，假如鏈表中有環，它們一定在環中相遇。
• 結論2：假設環的長度是n，先讓快指針走n步，然后快慢指針一起出發，每次一起走一步，最后一定相遇于環的入口節點。

解決這個問題可以分三步。

（1）第一步是確定一個鏈表中是否包含環。我們可以用兩個指針來解決這個問題。定義兩個指針，同時從鏈表的頭結點出發，一個指針一次走一步，另一個指針一次走兩步。如果走得快的指針追上了走得慢的指針，那么鏈表就包含環；吐過走得快得快的指針走到了鏈表的末尾（ListNode的next指向null）都沒有追上第一個指針，那么鏈表就不包含環。

（2）第二步是找到環中節點的數目，這一步的目的就是為尋找環的入口做鋪墊。我們在上面提到判斷一個鏈表里面是否有環時用到了一快一慢兩個指針。如果兩個指針相遇，則表明鏈表中存在環。兩個指針相遇的節點一定是在環中?？梢詮倪@個節點出發，一邊繼續向前移動一邊計數，當再次回到這個節點時，就可以得到環中節點數K （環的長度）。

（3）第三步是找到環的入口。我們還可以利用兩個指針來解決這個問題。?轉換為求環的倒數第N-K個節點.? ?先定義兩個指針P1和P2指向鏈表的頭結點。如果鏈表中的環有K個節點，則指針P1先在鏈表上向前移動K步，然后兩個指針以相同的速度向前移動。當第二個指針指向環的入口節點時，第一個指針已經圍繞著環走了一圈，又回到了入口節點(其實是鏈表的尾部)。

?

public ListNode EntryNodeOfLoop(ListNode head) {// 當頭結點為空或只有一個頭結點時，一定沒有環if (head == null || head.next == null)return null;ListNode low = head, fast = head;int cycleLength = 1;while (low != null && fast != null) {low = low.next;fast = fast.next.next;// 根據結論1，如果low和fast相遇，則鏈表中一定有環，可以順便計算環的長度if (low == fast) {fast = fast.next;while (low != fast) {fast = fast.next;cycleLength++;}break;}}// 如果鏈表沒有環，則low或fast指針到達鏈表末尾，為空if (low == null || fast == null)return null;// 重置low和fast指針，根據結論2尋找環的入口節點low = head; fast = head;while (cycleLength-- > 0)fast = fast.next;while (low != fast) {low = low.next;fast = fast.next;}return low; }

?

?

總結

以上是生活随笔為你收集整理的[链表]---链表中环的入口节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。