Problem 8.3 · Linked ListsEasy

Linked List Cycle

What it teaches: Floyd's cycle detection: a hash set uses O(n) memory; two runners at different speeds need O(1).

Practise it on judges as “Linked List Cycle”.

The problem

Given head, return true if the list has a cycle: some node can be reached again by following next. In the examples, pos is the index the tail links back to (−1 for no cycle); it's not passed to your method.

Example 1

Input: head = [3, 2, 0, -4], pos = 1
Output: true

The tail (−4) links back to node 2.

Example 2

Input: head = [1, 2], pos = 0
Output: true

Example 3

Input: head = [1], pos = -1
Output: false

Constraints

0 ≤ number of nodes ≤ 10⁴
O(1) memory follow-up

Pattern clues in the wording

→ Detect a loop in a chain of next pointers
→ O(1) memory asked

These clues point to Fast and Slow Pointers: Move one pointer one step and another two steps; their meeting (or the fast one finishing) reveals cycles and middles.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	head = [3,2,0,-4] pos = 1	true
2	head = [1,2] pos = 0	true
3	head = [1] pos = -1	false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Hash set of visited nodes · O(n)2. Optimal: Floyd's fast and slow · O(n)

Hash set of visited nodes

Time O(n) Space O(n)

Walk the list; if a node is already in the set, there's a cycle.

Approach 1

import java.util.HashSet;
import java.util.Set;

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

Verdict: Simple, but uses memory proportional to the list.

Optimal: Floyd's fast and slow

Time O(n) Space O(1)

slow +1, fast +2. If they ever point to the same node, there's a cycle. If fast reaches null, there isn't.

▶ Dry run: The fast runner laps the slow onehead = [3, 2, 0, -4], tail → node 1

↑slow↑fast

-4

null

Step 1/4Both at 3. (After −4 the list loops back to 2.)

Approach 2

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

Verdict: Constant memory.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty list
One node without a cycle
One node pointing to itself
Cycle starting at the head

Mistakes people make

Comparing slow.val == fast.val (different nodes can hold equal values).
Missing the fast != null check.

Interview

Follow-up questions

How do you find the node where the cycle begins?

How do you find the cycle's length?

Command Palette