链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null

解题思路

有重复就要想到 HashMap，第一种方法遍历链表，并在 HashMap 中存储值，如果有重复值则对应的结点为环的入口结点

import java.util.HashMap;
public class Solution {

    private HashMap<Integer, Object> map = new HashMap<>();

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null || pHead.next == null) {
            return null;
        }
        ListNode p = pHead;
        while(p != null) {
            if(map.containsKey(p.val)) {
                return p;
            }
            map.put(p.val, null);
            p = p.next;
        }
        return null;
    }
}

还可以使用快慢指针法，设置快慢指针，都从链表头出发，快指针每次走两步，慢指针每次走一步，假如有环，一定相遇于环中某点。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终会相遇于环入口。根据上述我们可以总结出两个结论：

• 设置快慢指针，假如有环，他们最后一定相遇
• 两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口

首先证明结论一：设置快慢指针 fast 和 low，fast 每次走两步，low 每次走一步。假如有环，两者一定会相遇，因为 low 一旦进环，可看作 fast 在后面追赶 low，每次两者都接近一步，最后一定能追上

然后证明结论二，假设：

• 链表头到环入口长度为 a
• 环入口到相遇点长度为 b
• 相遇点到环入口长度为 c
  

则相遇时：

• 快指针路程 = a+(b+c)k+b，其中 k 为绕环的圈数且 k >= 1（即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾），b+c 为环的长度
• 慢指针路程 = a+b

而快指针走的路程是慢指针的两倍，所以：(a+b)*2 = a+(b+c)k+b，化简可得 a=(k-1)(b+c)+c，这个式子的意思是： 链表头到环入口的距离 = 相遇点到环入口的距离 + (k-1) 圈环长度。其中 k >= 1，所以 k-1 >= 0 圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口

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