142.md

142. Linked List Cycle II

Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return null

Thinking Process

1. Using two pointers, we can determine if there is a cycle in the list
2. When the two pointers meet, the fast pointer will travel 1 more cycle than the slower pointer.
3. Assume the cycle begins at position A, and slow pointer is at position A + B when the two pointers meet
4. The fast pointer would have travelled 2(A+B) distance when the pointers meet, which means that the cycle length is (A+B)
5. Hence after travelling another A step, the slow pointer will reach the head of the cycle

Code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode n1 = head;
        ListNode n2 = head;
        while(n1 != null && n2 != null){
            n1 = n1.next;
            n2 = (n2.next != null) ? n2.next.next : null;
            if(n1 == n2 && n1 != null){
                while(n1 != head){
                    n1 = n1.next;
                    head = head.next;
                }
                return head;
            }
        }
        return null;
    }
}

Complexity

1. Space complexity is O(1)
2. Time complexity is O(n)