1. 快慢指针+同速双指针

1.1 分析

• 先利用快慢指针判断是否有环，如果有，两者会在环中相遇。
  

• 再利用同速双指针，分别从相遇点和链表头出发，两者一定在环入口相遇。
  证明：
  快指针的路程：s1 = a + k1(b+c) + b
  慢指针的路程：s2 = a + k2(b+c) + b , 令k2 - k1 = k ,则 k >= 1。
  因为速度是慢指针的2倍, 所以s1 = 2 * s2，
  则，a + k1(b+c) + b =2 * （ a + k2(b+c) + b）
  简化，a + b = k (b + c)
  即 a = (k-1)(b+c) +c
  这说明，从头结点和相遇点出发，两只同速指针一定在环入口相遇。

  1.2 代码

  public class Solution {
  
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null ||pHead.next == null) return null;
        ListNode node1 = pHead;
        ListNode node2 = pHead;
        while(node1!=null && node1.next!=null){
            //先寻找是否有环
            //快慢指针一起出发
            node1 = node1.next.next;
            node2 = node2.next;
            if(node1 == node2){//如有环，快慢指针在环中某个结点相遇
                //使用同速的双指针，找到环的入口
                //起点分别是head和环中相遇点
                node2=pHead;
                while(node1 != node2){
                    node1= node1.next;
                    node2 = node2.next;
                }
                return node1;
            }            
        }
        return null;
    }
  }

  1.3 复杂度

  空间：O(1)
  时间：O(n)

  2.快慢指针+环长+双指针

  2.1 分析

• 同方法一，先判断是否有环

• 如果有环，计算环的长度n

• 双指针，都从头结点出发，一个先走n步，然后一起同速出发，最终会在换入口相遇。

  2.2 代码

  public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null ||pHead.next == null) return null;
        ListNode node1 = pHead;
        ListNode node2 = pHead;
        while(node1!=null && node1.next!=null){
            //先寻找是否有环
            //快慢指针一起出发
            node1 = node1.next.next;
            node2 = node2.next;
            if(node1 == node2){//如有环，快慢指针在环中某个结点相遇
                //计算环得长度
                int len = 1;
                node1 = node1.next;
                while(node1 != node2){
                    node1 =node1.next;
                    len++;
                }
                //双指针找换入口
                //一个指针先走len步
                for(node1 = pHead; len > 0; node1 = node1.next, len--){};
                //双指针同速前进,直到相遇
                node2 = pHead;
                while(node1 != node2){
                    node1=node1.next;
                    node2=node2.next;
                }
                return node1;
            }
        }
        return null;
    }
  }

  2.3 复杂度

  空间：O(1)
  时间：O(n)

  3. HashSet

  3.1 分析

  利用Set去重的特性，注意，set中的重复需要两个结点的hashcode()和equial()都相等。

  3.2 代码

  import java.util.HashSet;
  public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null ||pHead.next == null) return null;
        ListNode tmp = pHead;
        HashSet<ListNode> set = new HashSet<>();
        while(tmp != null){
            if(!set.add(tmp)){
            return tmp;
            }
            tmp =tmp.next;
        }
        return null;
    }
  }

  3.3 复杂度

  空间：O(n)
  时间: O(n)