链表中环的入口结点

方法一：哈希（HashSet）

思路：就是用hashset的查重功能，从头结点开始，将set中不存在的节点就放入到set中，否则就将第一个重复的点输出，就是链表的环的入口节点

代码：

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) {
         ListNode fast=pHead;
         ListNode slow=pHead;
         while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
         }
         if(fast==null||fast.next==null){
            return null;
         }
         fast=pHead;
         while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
         }
         return fast;


    }
}

方法二：快慢指针

思路：

1.设置两个指针：一个快指针每次走两个节点，慢指针每次走一个节点

2.找出相遇的点，经过计算可以发现链表的头结点距离环的入口节点的距离等于相遇的点距离环的入口节点

3.所以让fast从表头开始，slow从相遇的点开始，以相同的速度进行移动，则相遇的点就是链表环的入口节点

4，注意判断如果fast==null||fast.next==null，那么就表明该链表不存在环，返回null

图解：

链接

代码：

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) {
        //设置快慢指针，都指向头结点
         ListNode fast=pHead;
         ListNode slow=pHead;
         //只要fast和fast.next不等于null
         //那么就让fast每次移动两个节点，slow每次移动一个节点
         //如果两者相遇了，就退出
         while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
         }
         //如果是因为遇到null而退出，那么就返回null，表示链表没有环
         if(fast==null||fast.next==null){
            return null;
         }
         //否则经过计算发现，链表的头结点距离环的入口节点的距离等于相遇节点与环的入口节点的距离
         //所以让fast=pHead,然后让两者同时出发，并且以相同的速度进行移动，则相遇的地方就是环的入口节点
         fast=pHead;
         while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
         }
         return fast;


    }
}