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

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) {
        //方法一：哈希法，通过遍历链表，将链表中的节点保存在哈希集合中，在把节点保存到集合之前,需要检验集合中是否已经存在。
        //如果存在，则表示链表存在环，且第一个重复的节点就是环的入口节点；如果不存在，则将该节点保存到集合中。
//         //特殊值处理，空链表
//         if(pHead == null){
//             return null;
//         }
        
//         HashSet<ListNode> hashSet = new HashSet<>();//创建一个对象HashSet
//         ListNode head = pHead;
//         //循环遍历，直到遇到第一个相同的节点，即为链表中环的入口节点
//         while(head != null){
//             //判断集合中是否存在当前节点
//             if(hashSet.contains(head)){//集合中存在当前节点
// //                 return head;
//                 break;
//             }else{//集合中不存在当前节点
//                 hashSet.add(head);
//                 head = head.next;
//             }
//         }
        
//         return head;
        
        //方法二：双指针法，定义两个指针，分别是快指针和慢指针
        //特殊值处理，空链表
        if(pHead == null){
            return null;
        }
        
        ListNode fast = pHead;
        ListNode slow = pHead;
        //通过循环遍历，找到相遇的节点C(如果链表中存在环)
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //退出循环时如果fast或者fast.next为空，则不存在环
        if(fast == null || fast.next==null){
            return null;
        }
        
        fast = pHead;//链表中存在环，更新快指针为头指针,
        //快指针与慢指针以相同的速度从头指针处遍历链表，慢指针在相遇节点C处遍历链表，再次相遇时的节点即为链表中的环的入口节点。
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        
        return fast;
    }
}