题解 | #链表中环的入口结点#

这道题告诉我两件事情，一是一些题没有数学思维就不好办，不会就记下来（比如根据相遇点和起始点找环入口点）；二是别乱加逻辑（见下面的代码）。

(已通过）
/*
 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) return null;
        if(pHead.next == pHead) return pHead;
        if(pHead.next == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast != null && fast.next != null){
            // 这里不要乱加逻辑
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        if(fast == null || fast.next == null) return null;
        while(pHead != fast){
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }
}

而一开始我的逻辑是这样的：

/*
 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) return null;
        if(pHead.next == pHead) return pHead;
        if(pHead.next == null) return null;
        ListNode fast = pHead; // 1
        ListNode slow = pHead; // 2
        while(fast != null && fast.next != null){
            if(fast != slow){ // 3
                fast = fast.next.next;
                slow = slow.next;
            }
            else{
                break;
            }
        }
        if(fast == null || fast.next == null) return null;
        while(pHead != fast){
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }
}

上面的代码问题在于 1 和 2 表明快慢指针一开始处于同一个位置，导致 3 处的循环一开始就没进去过，直接导致 break 退出循环，所以值永远是第一个节点。
如果快慢指针起始位置改成不一样呢？能行吗？

/*
 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) return null;
        if(pHead.next == pHead) return pHead;
        if(pHead.next == null) return null;
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while(fast != null && fast.next != null){
            if(fast != slow){ // 1
                fast = fast.next.next;
                slow = slow.next;
            }
            else{
                break;
            }
        }
        if(fast == null || fast.next == null) return null;
        while(pHead != fast){
            pHead = pHead.next;
            fast = fast.next;
        }
        return pHead;
    }
}

答案是不行，会死循环，因为快慢指针一般都是指向同一个节点，这样才能保证后面每次快指针都比慢指针稳定拉开 1 步距离。而如果一开始快指针就在慢指针前面，就会导致两者相差 2，会造成快指针刚好错开相遇点（起始距离是 2，相当于走了两步），永远也无法跟慢指针相遇（哪怕循环里没乱加逻辑）。