Cycle in LL

是否有环

• 快慢指针相交即有环
• HashSet

环的具体位置

起点在哪

• HashSet 仍然试用
• 画图进行数学推导（参见下图，可以发现此时只需要在快慢指针相遇的时候，利用x1==x3，从LL到head再起一个指针按照同样的速度与slow指针一起同时往前走，当他们相遇的时候，就是相遇的地方）

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) return null;
    ListNode slow = head, fast = head, start = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            while (slow != start) {
                slow = slow.next;
                start = start.next;
            }
            return start;
        }
    }
    return null;
}

Cycle多长

To understand this solution, you just need to ask yourself these question. Assume the distance from head to the start of the loop is x1 the distance from the start of the loop to the point fast and slow meet is x2 the distance from the point fast and slow meet to the start of the loop is x3 What is the distance fast moved? What is the distance slow moved? And their relationship?

1. x1 + x2 + x3 + x2
2. x1 + x2
3. x1 + x2 + x3 + x2 = 2 (x1 + x2)

要计算环的长度可以在相遇后，让fast保持不懂，slow继续往前走，知道再次相遇走过的距离即为环的长度。