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

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) {
        //根据上一篇帖子求出的公式，i=tkn，当快慢指针相遇时，tk肯定为整数，，即i为环的长度的整数倍
        ListNode fastNode = pHead, slowNode = pHead;
        int i = 0;
        i++;
        slowNode = slowNode.next;
        if (slowNode == null ) return null;
        fastNode = fastNode.next.next;
        if (fastNode == null) return null;
        while (fastNode != slowNode) {
            i++;
            slowNode = slowNode.next;
            if (slowNode == null) return null;
            fastNode = fastNode.next.next;
            if (fastNode == null) return null;
        }
        //用步差为i的快慢指针遍历链表，指针会在环的第一个节点重合。
        fastNode = pHead;
        slowNode = pHead;
        for (int j = 0; j < i; j++) fastNode = fastNode.next;
        while (fastNode != slowNode) {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        return fastNode;
    }
}

前题有判断链表是否有环的解法。快慢指针在第一次相遇时，慢指针走的步数一定是环长度的整数倍。求出这个值i，然后用步差为i的快慢指针遍历，会在环的第一个节点相遇。