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

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
/*
链表中没有环，则指针遍历会遇到null

在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。快指针一共走了x+n(y+z)+y步，慢指针一共走了x+m(y+z)+y，这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)，这时候x+y=(n−2m)(y+z)，因为环的大小是y+z，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这y个节点，那说明这y个节点它们就是重叠遍历的，那它们从入口位置就相遇了

时间复杂度：O(n)，最坏情况下遍历链表两次
空间复杂度：O(1)，使用了常数个指针，没有额外辅助空间
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode nodeQ = pHead;
        ListNode nodeS = pHead;
        ListNode meet1 = null;//此处命名为meet1是因为这是题中第一次相遇点，返回点为第二次相遇点
        while (nodeQ != null){
            if (nodeQ.next == null){
                return null;
            }
            nodeQ = nodeQ.next;
            if (nodeQ.next == null){
                return null;
            }
            if (nodeQ.next == nodeS.next){
                meet1 = nodeS.next;
                break;
            }
            nodeQ = nodeQ.next;
            nodeS = nodeS.next;
        }
        System.out.print(meet1.val);
        while (pHead != null){
            if(pHead == meet1){
                return pHead;
            }
            pHead = pHead.next;
            meet1 = meet1.next;
            System.out.print("meet1:");
            System.out.println(meet1.val);
            System.out.print("pHead:");
            System.out.println(pHead.val);
        }
        return null;
    }
}