Linked List Cycle II

Medium Linked List Slow Fast Pointers Original on LeetCode

Linked List Cycle II is a medium linked list problem solved with the slow fast pointers pattern. The best approach, optimal (floyd, then reset one pointer), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from hash set up.

Problem

Return the node where a linked list’s cycle begins, or null if there is no cycle. Do not modify the list.

Examples

Example 1

Input: head = [3, 2, 0, -4], tail connects to index 1
Output: the node with value 2

Example 2

Input: head = [1, 2], no cycle
Output: null

Constraints

The list has 0 to 10^4 nodes.
Do not modify the list. Follow-up: O(1) memory.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Hash set	`O(n)`	`O(n)`
Optimal (Floyd, then reset one pointer)	`O(n)`	`O(1)`

1Hash set

TimeO(n)

SpaceO(n)

The first node you visit twice is where the cycle begins.

Walk the list adding nodes to a set; return the first repeated node.

Java

class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        for (ListNode p = head; p != null; p = p.next)
            if (!seen.add(p)) return p;
        return null;
    }
}

2Optimal (Floyd, then reset one pointer)

TimeO(n)

SpaceO(1)

Find a meeting point with slow and fast. If the head is a steps from the cycle start and they meet b steps into the cycle of length c, then 2(a + b) = a + b + k·c, so a = k·c - b. A pointer from the head and one from the meeting point, both moving one step, meet at the cycle start.

Run slow and fast until they meet (or return null).
p = head; while p != slow: p = p.next; slow = slow.next.
Return p.

Java

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;
    }
}

Edge cases to test

The cycle starts at the head
Self-loop on a single node

Hints

Hint 1

After slow and fast meet, the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (going around).

FAQ

What is the best time complexity for Linked List Cycle II?

Optimal (Floyd, then reset one pointer) runs in O(n) time and O(1) extra space.

Which pattern does Linked List Cycle II use?

It is a linked list problem that uses the slow fast pointers pattern. Other problems with the same pattern: Middle of the Linked List, Linked List Cycle.

Is there a brute force solution for Linked List Cycle II?

Yes. Hash set takes O(n) time and O(n) space. The first node you visit twice is where the cycle begins.

Which edge cases should I test for Linked List Cycle II?

The cycle starts at the head; Self-loop on a single node.