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

解题方法一：

利用HashSet集合的不重复特性，判断链表环中第一次重复的节点是否存在。

当set.contains(pHead) 为true时，说明第一次重复节点出现。即为链表环的入口节点。

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) {
        //环的入口节点特点：有两个链表的指针都指向同一节点
        //在环内循环时，第一次重复的结点即为入口节点
        HashSet<ListNode> set = new HashSet<>();
        //HashSet集合的特点：无序，不重复，无索引

        while(pHead != null){
            //当set中包含节点时，说明出现重复节点
            if(set.contains(pHead)){
                return pHead;
            }
            //set中加入未重复的结点
            set.add(pHead);
            pHead = pHead.next;

        }


        return null;
    }
}

方法二：快慢指针法

        //假设从头节点到环入口节点之间走过的距离为x，头节点到快慢指针第一次相遇的节点距离为y

        //因为快指针的速度为慢指针的两倍

        //所以此时快指针走的距离为2（x+y），慢指针走的距离为x+y

        //让快指针此时指向头节点，慢指针指向第一次相遇的节点

        //距离环入口节点的距离都为x

        //所以此时第一次相遇的节点，即为入口节点

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null){
            return null;
        }

        ListNode fast = pHead;
        ListNode slow = pHead;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            //记录快慢指针第一次相遇的节点
            if(slow == fast){
                break;
            }
        }

        fast = pHead;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}