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

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //快结点走两步，慢结点走一步
        //  a
        //o->o->o->o->o
        //  c   |     |   b
        //      o<-o<-o
        //头结点到环起始点距离为a
        //有个相遇点，从环起始点到这距离为b，再从这转到起始点距离为c
        //环长度为b+c
        //相遇时，慢结点走的距离为a+b
        //快结点走了 a+b+c+b
        //因为快结点一定比慢结点快一倍 a+b+c+b是a+b的2倍，则c=a
        //相遇点到环起始点距离=头结点到环起始点距离
        ListNode quickNode = pHead;
        ListNode slowNode = pHead;
        ListNode meetNode = null;
        while (quickNode != null && slowNode != null) {
            if (quickNode.next != null) {
                quickNode = quickNode.next.next;
            }
            slowNode = slowNode.next;
            if (quickNode == slowNode) {
                //相遇了，记录下相遇的结点
                meetNode = quickNode;
                System.out.println("相遇" + meetNode.val);
                break;
            }
        }
        if (meetNode != null) {
            slowNode = pHead;

            if (meetNode.next == null || slowNode.next == null) {
                return meetNode;
            }
            while (meetNode != slowNode) {
                meetNode = meetNode.next;
                slowNode = slowNode.next;
            }
            return meetNode;
        }

        return null;
    }
}