【每日一題】【快慢指針相遇】2022年1月25日-NC3 連結清單中環的入口結點

描述

給一個長度為n連結清單，若其中包含環，請找出該連結清單的環的入口結點，否則，傳回null。

答案：

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) {
                fast = pHead;
                //在快慢指針相遇點開始，往後找，直到相遇，即為入口節點
                while(fast != null && slow != null) {
                    if(fast == slow) {
                        return slow;
                    }
                    fast = fast.next;
                    slow = slow.next;
                }
            }
        }
        return null;
    }
}