描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n <= 10000，1<= 结点值 <= 10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

思路1：集合Set

使用集合存储，再次遍历判断是否存在重复节点（不满足空间复杂度要求）

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

思路2：节点记忆

节点记忆，类似Set，只不过不创建新空间，直接利用原节点存储。

由于1<=节点值<=10000，可以遍历给每个节点存储的值+10000，当遇到第一个值大于10000的节点，则为入口，再恢复成原来的值

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        while(pHead != null) {
            if(pHead.val > 10000) {
                pHead.val = pHead.val - 10000;
                return pHead;
            }
            pHead.val = pHead.val + 10000;
            pHead = pHead.next;
        }
        return null;
    }
}

思路3：快慢指针

步骤：

1. 快指针一次走2步，慢指针一次走1步
2. 相遇时让快指针回到头节点，二者再以相同的速度前进，再次相遇时即为入口节点

原理：

1. 假设头节点到入口节点距离为x，入口节点到第一次相遇节点距离为y
2. 此时假设快指针比慢指针多跑了一圈，则环的周长=x+y
3. 慢指针在y处，再走x步回到入口节点
4. 快指针回到起点，再走x步同样到入口节点

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode p1 = pHead;
        ListNode p2 = pHead;              
        if(p1 == null || p1.next == null) {
            return null;
        }        
        while(p1 != null && p1.next != null) {
            //避免判断到头节点
            p1 = p1.next.next;
            p2 = p2.next;
            if(p1 == p2) {//第一次相遇
                break;
            }
        }
        if(p1 == null || p1.next == null) {
            return null;
        }
        p1 = pHead;
        while(p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}