Sweaty Imposter

Linked List Cycle II

MediumFast & Slow Pointers (Floyd's)NeetCode 150MidOpen on LeetCodeUpdated

You're given the head of a singly linked list that may contain a cycle. Return the node where the cycle begins: the node the tail links back to, which is also the first node of the loop you reach from the head. Return null if there is no cycle. The examples write the list as values plus pos, the index the tail links back to (-1 for none), and name the returned node by its index. Don't modify the list. Can you use O(1) extra memory?

Examples

head = [3,2,0,-4], pos = 1 returns node at index 1

320-4
The loop is entered at index 1 (value 2).

The tail, -4, links back to the node with value 2 at index 1. Walking from the head, that's the first node you reach that belongs to the loop, so it's the one returned.

head = [1,2], pos = 0 returns node at index 0

12
The tail links to the head, so the loop starts at index 0.

The tail, 2, links back to the head, so the whole list is the loop and the cycle begins at the head itself (index 0).

head = [1], pos = -1 returns null

The only node's next is null, so there is no cycle and the answer is null.

Constraints

  • 0 <= n <= 10^4

Hints

Hint 1

Once two runners meet inside a loop, is there a way to back out exactly where the loop began?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Run slow (one step) and fast (two steps) until they meet inside the cycle. If the entrance is a steps from the head and they meet b steps past it, slow has walked a + b and fast 2(a + b), so a + b is a whole number of laps. Walking a more steps from the meeting point therefore lands on the entrance. Restart one pointer at the head, step both by one, and they meet exactly there.

Time

O(n)

Space

O(1)

Pitfall

The first meeting point is usually not the entrance. For [3,2,0,-4] with pos = 1 the two pointers first meet at -4 (index 3), so returning there is wrong; the second walk from the head is what reaches index 1.

Solutions

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