給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出 null
解題思路
有重復就要想到 HashMap，第一種方法遍歷鏈表，并在 HashMap 中存盤值，如果有重復值則對應的結點為環的入口結點
import java.util.HashMap;
public class Solution {
private HashMap<Integer, Object> map = new HashMap<>();
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead == null || pHead.next == null) {
return null;
}
ListNode p = pHead;
while(p != null) {
if(map.containsKey(p.val)) {
return p;
}
map.put(p.val, null);
p = p.next;
}
return null;
}
}
還可以使用快慢指標法，設定快慢指標，都從鏈表頭出發，快指標每次走兩步，慢指標每次走一步，假如有環，一定相遇于環中某點，接著讓兩個指標分別從相遇點和鏈表頭出發，兩者都改為每次走一步，最侄訓相遇于環入口，根據上述我們可以總結出兩個結論：
- 設定快慢指標，假如有環，他們最后一定相遇
- 兩個指標分別從鏈表頭和相遇點繼續出發，每次走一步，最后一定相遇與環入口
首先證明結論一：設定快慢指標 fast 和 low，fast 每次走兩步，low 每次走一步，假如有環，兩者一定會相遇，因為 low 一旦進環，可看作 fast 在后面追趕 low，每次兩者都接近一步，最后一定能追上
然后證明結論二，假設：
- 鏈表頭到環入口長度為 a
- 環入口到相遇點長度為 b
- 相遇點到環入口長度為 c
則相遇時：
- 快指標路程 = a+(b+c)k+b，其中 k 為繞環的圈數且 k >= 1（即最少一圈，不能是0圈，不然和慢指標走的一樣長，矛盾），b+c 為環的長度
- 慢指標路程 = a+b
而快指標走的路程是慢指標的兩倍，所以：(a+b)*2 = a+(b+c)k+b，化簡可得 a=(k-1)(b+c)+c，這個式子的意思是： 鏈表頭到環入口的距離 = 相遇點到環入口的距離 + (k-1) 圈環長度，其中 k >= 1，所以 k-1 >= 0 圈，所以兩個指標分別從鏈表頭和相遇點出發，最后一定相遇于環入口
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(slow == fast) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
slow = pHead;
while(slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235928.html
標籤：其他
上一篇：字符流中第一個不重復的字符
下一篇：Unity射擊實體講解—主角創建