环形链表

题目的意思是找到第一个环的入口点，当然，如果可以使用哈希表的话可以很快的找到，但是哈希表需要占用额外的空间复杂度，所以我们不希望使用哈希表来进行辅助查找。

龟兔赛跑

不使用额外循环的方法其实还是快慢指针，只不过这里有一个技巧，就是怎么找到入环点。技巧就是当快慢指针相遇后，慢指针从头节点开始，再次相遇的位置就是入环点，当然，具体证明过程有点复杂，还是只记住这个技巧吧。

解题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (slow != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }
}