題目描述
給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null，
思路
快慢指標， 快指標步長2，慢指標步長1，如果存在環，快指標總能追上慢指標， 先找到快慢指標相遇的點p，并假設環的入口在點q， 從頭節點到點q距離為A，q->p距離為B，p->q距離為C， 因為快指標是慢指標的兩倍速，且在p點相遇，則可以得到等式 2(A+B) = A+B+C+B. 由等式可得，C = A， 此時slow指標已經在p，可以讓fast回傳頭節點以步長1開始走，原slow指標繼續保持原來的走法， fast與slow再次相遇時，因為A=C，所以相遇的點一定是q，時間復雜度O(n)，空間復雜度O(1)，
代碼
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = pHead;
ListNode fast = pHead;
while(fast != null) {
if(fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
fast = pHead;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
筆記
除了相遇，其余情況都回傳null，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79571.html
標籤：其他
上一篇：《演算法導論》圖相關演算法小結
下一篇：洗掉鏈表中重復的結點