劍指offer-連結清單中環的入口節點

題目描述

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

思路

（1）第一步是确定一個連結清單中是否包含環。我們可以用兩個指針來解決這個問題。定義兩個指針pfast和pslow，同時從連結清單的頭結點pHead出發，pslow一次走一步，pfast一次走兩步。

如果pfast追上了pslow(pfast == pslow)，那麼連結清單就包含環；pfast走到了連結清單的末尾都沒有追上pslow，那麼連結清單就不包含環。

（2）第二步是确定環中節點的數目，當pfast == pslow時，假設pslow走過x個節點，則pfast走過2x個節點。設環中有n個節點，因為pfast比pslow多走一圈（n個節點），

是以有等式2x = n + x，可以推出n = x，即pslow走了一個環的步數n

（3）第三步是找到環的入口。當pfast == pslow 時，pslow走了一個環的步數n,即Pslow先在連結清單上向前移動一個環的步數n步，pslow的位置不變,pfast重新指向連結清單頭部pHead，然後pslow和pfast一起向前每次走一步 (速度相同),直到pfast == pslow(相遇)，此時兩個指針相遇的節點就是環的入口

(pfast指向環的入口節點時，pslow已經圍繞着環走了一圈，又回到了入口節點,因為pslow先走了一個環的步數)

java實作

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead) {
            if (pHead == null || pHead.next == null || pHead.next.next == null)
                return null;//0,1,2個節點不存在環
            ListNode pslow = pHead.next;
            ListNode pfast = pHead.next.next;
            while (pfast != null) {
                if(pfast==pslow){//快指針追上滿指針說明有環
                    pfast=pHead;//pfast重新指向連結清單頭部pHead
                    //pslow和pfast一起向前每次走一步 (速度相同),直到pfast == pslow(相遇)
                    while (pfast!=pslow){
                        pfast=pfast.next;
                        pslow=pslow.next;
                    }
                    return pfast;//pfast == pslow，此時兩個指針相遇的節點就是環的入口
                }
                pfast=pfast.next.next;//快指針一次走兩步
                pslow=pslow.next;//慢指針一次走一步
            }
            return null;
        }
    }
           

參考

https://www.jianshu.com/p/092d14d13216

https://blog.csdn.net/kongmin_123/article/details/82313198