142.Linked List Cycle II

Posted on | In

Solution 1: accepted 1ms

  1. A: the distance from the beginning to the start of the cycle
  2. B: the distance slow pointer moved the start of the cycle
  3. L: the length of the cycle

So the slow pointer has moved A+B, therefore the fast pointer 2A+2B. Since the fast pointer have moved L more steps, we have A+B+L=2A+2B –> L=A+B. Since L=A+B, the slow pointer has moved B, the rest of the cycle(back to the starting point) is A, the same as the distance from head to the start of the cycle. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode detectCycle(ListNode head) {
    ListNode dummy = new ListNode(0);  // no need to introduce dummy
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            ListNode start = dummy; // start with dummy
            while (slow != start) {
                slow = slow.next;
                start = start.next;
            }                
            return start;
        }
    }
    return null;
}

Without dummy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            ListNode start = head;
            while (slow != start) {
                slow = slow.next;
                start = start.next;
            }                
            return start;
        }
    }
    return null;
}