解法1:边遍历边删除（边标记）

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        if (pHead.next == pHead) {
            return pHead;
        }
        ListNode next = pHead.next;
        pHead.next = pHead;
        return EntryNodeOfLoop(next);
    }
}

删除就是说让这个节点的next指向这个节点本身，当然也可以用其他的方法来做标记

如果遍历到某个节点，发现它已经被删除了，那就是环的第一个节点

时间复杂度O(n)

空间复杂度O(1)

解法2:哈希表

不考虑空间复杂度的情况下可以用这个

import java.util.*;
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pHead != null) {
            if (visited.contains(pHead)) {
                return pHead;
            }
            visited.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }
}

时间复杂度O(n)

空间复杂度O(n)

解法3:快慢指针

思路：

快指针fast一次走2步，慢指针slow一次走一步，快慢指针相遇时说明有环的存在。

假设在环外有a个节点，在环内走了b个节点, 慢指针还有c个节点没有走

那么相遇的时候，快指针走了a+b+c+b, 慢走了a+b

因为快指针走的是慢指针的两倍，所以a + b + c + b =2 (a + b) = a + b + a + b，也就是c = a;

慢指针再走c步就能到环的入口，也就是再走a步即可；

让快指向头节点，再重新一步一步走，当快指针和慢指针相遇的时候，慢指针走了a步，也正好到入口节点

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        while (fast != null && slow != fast) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
        }
        if (fast == slow ) {
            fast = pHead;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
        }

        return fast;

    }
}