What is the brute force approach and complexity for Linked List Cycle?

Hash set of node pointers; seeing a node twice means a cycle with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Linked List Cycle?

slow moves 1, fast moves 2; they meet only if there is a cycle with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Linked List Cycle?

Look for key signals in the prompt: "determine if the list has a cycle" indicates We only need yes/no, not where the loop is → two pointers can answer it.; "linked list, follow next" indicates Each node has exactly one next, so the walk is a path that either ends or bends into one loop (a "ρ" shape).; "O(1) memory follow-up" indicates No visited set → let a fast and a slow pointer find the repeat for us..

Linked List Cycle

Easy·LeetCode #141Basic Anchor

LeetCode

Jump:

30-Second Mental ModelFast & Slow pointers — cycle detection (Floyd)

Complexity:O(N)→O(N)

Key Insight

Start two pointers at head. Each move, slow goes 1 step and fast goes 2 steps. If the list ends, fast reaches null first and we return false. If there is a loop, both pointers end up going round it, and fast gets 1 node closer to slow every move, so it must land exactly on slow. Then we return true.

Core Validity Invariant

There is a cycle exactly when slow and fast land on the same node; if fast or fast->next becomes null, the list has an end.

Problem

You are given head, the first node of a singly linked list.

The list has a cycle if you can keep following next pointers forever, because some node's next points back to a node that came earlier. Return true if the list has a cycle, and false if following next eventually reaches null.

pos in the examples is only used to build the test list: it is the index of the node the tail links back to (-1 means no cycle). Your function does not receive it.

Input

head — the first node of the list (it can be null).

Output

true if the list contains a cycle, otherwise false.

Example 1

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

Output: true

The tail (-4) links back to the node at index 1 (value 2), so 2 → 0 → -4 → 2 → … repeats forever.

Example 2

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

Output: true

The tail (2) links back to the head (1).

Example 3

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

Output: false

One node whose next is null. The walk ends, so there is no cycle.

Constraints

• The number of nodes is in the range [0, 10^4]
• −10^5 ≤ Node.val ≤ 10^5
• pos is −1 or a valid index in the list
• Follow-up: can you solve it using O(1) extra memory?

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If there is no cycle, what does the walk along next eventually reach?
2.
If there is a cycle, what happens to that walk instead?
3.
To notice a repeat, what exactly should I remember about each node — its value, or the node itself?
4.
Could two different nodes hold the same value? What would that do to a check based on values?
5.
Without any memory, how could two walkers tell me they are going round in a circle?

Brute force approach

Idea

Walk the list and put each node's address into a hash set. If we arrive at a node that is already in the set, we have gone round in a loop. If we reach null, the list ends and there is no cycle.

Thinking process

1
A cycle means the walk comes back to a node it has already visited.
2
So the most direct check is: remember every node, and see if we ever revisit one.
3
Values can repeat (two different nodes can both hold 7), so the thing to remember is the node itself — its pointer.
4
Each node is checked once, so the walk ends after at most n + 1 moves.

Visual

Green = a new node added to the set. Orange = a repeated value on a new node (not a cycle). Purple = a node seen twice (the cycle). "↩ 3" means the tail's next is node 3.

Hash set of visited nodeshead = [3, 2, 0, 2, 5, 1, 4, 6], pos = 3step 1/9

list

↩ 3

▲cur

idx

seen (node pointers)

node 0 (val 3)

node 0 is new → add it

node 0 is not in the set yet. Add it and move to its next.

Code & Implementation

brute.cpp

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // Remember every node we have stood on — by its ADDRESS, not its value.
        unordered_set<ListNode*> seen;

        ListNode* cur = head;
        while (cur != nullptr) {
            // Standing on a node we already visited means the list looped back.
            if (seen.count(cur)) return true;
            seen.insert(cur);
            cur = cur->next;
        }
        // We reached null: the list has an end, so there is no cycle.
        return false;
    }
};

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

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        // Remember every node we have stood on — by its reference, not its value.
        Set<ListNode> seen = new HashSet<>();

        ListNode cur = head;
        while (cur != null) {
            // Standing on a node we already visited means the list looped back.
            if (seen.contains(cur)) return true;
            seen.add(cur);
            cur = cur.next;
        }
        // We reached null: the list has an end, so there is no cycle.
        return false;
    }
}

from typing import Optional, List, Dict, Set, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Remember every node we have stood on — by its reference, not its value.
        seen: Set[ListNode] = set()

        cur = head
        while cur is not None:
            # Standing on a node we already visited means the list looped back.
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next

        # We reached null: the list has an end, so there is no cycle.
        return False

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function hasCycle(head: ListNode | null): boolean {
    // Remember every node we have stood on — by its reference, not its value.
    const seen = new Set<ListNode>();

    let cur = head;
    while (cur !== null) {
        // Standing on a node we already visited means the list looped back.
        if (seen.has(cur)) return true;
        seen.add(cur);
        cur = cur.next;
    }
    // We reached null: the list has an end, so there is no cycle.
    return false;
}

Complexity

Time O(N)Space O(N)

The time is already fine. The cost is memory: the set can hold all n node pointers. The follow-up asks for O(1) memory.

Optimized approach

Idea

Start from brute force

The brute force walks once and stores every node it passes, so it can spot the first repeat.

Find the repeated work

We do not need to know which node repeats, only whether something repeats. Storing all n nodes just to answer yes/no is wasted memory.

Define the state — what variables do I need?

slow: Moves 1 node per step.
fast: Moves 2 nodes per step. It is always ahead of slow, so it is the one that can hit null.

Define validity

There is a cycle exactly when slow and fast land on the same node; if fast or fast->next becomes null, the list has an end.

Define the transitions — when does each pointer move, and why is it safe?

Every step, while fast and fast->next are not null

slow = slow->next; fast = fast->next->next

We check fast first and then fast->next, so both hops of fast are on real nodes. Slow follows a path fast already walked, so it is safe too.

slow == fast after a move

return true

Two pointers moving forward at different speeds can only stand on the same node again if the path bends back on itself.

fast == null or fast->next == null

return false

fast found the end of the list. A list with an end has no cycle.

What does the current window add to the answer?

Each move either brings fast closer to the end of the list or (inside a loop) 1 node closer to slow. Either way the loop ends with the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // fast moves 2 steps, so check fast AND fast->next before moving it.
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // 1 step
            fast = fast->next->next;    // 2 steps

            // Inside a loop, fast gains 1 node on slow every move,
            // so it must land on slow eventually.
            if (slow == fast) return true;
        }
        // fast fell off the end: the list has an end, so no cycle.
        return false;
    }
};

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // fast moves 2 steps, so check fast AND fast.next before moving it.
        while (fast != null && fast.next != null) {
            slow = slow.next;         // 1 step
            fast = fast.next.next;    // 2 steps

            // Inside a loop, fast gains 1 node on slow every move,
            // so it must land on slow eventually.
            if (slow == fast) return true;
        }
        // fast fell off the end: the list has an end, so no cycle.
        return false;
    }
}

from typing import Optional, List, Dict, Set, Tuple

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        # fast moves 2 steps, so check fast AND fast.next before moving it.
        while fast is not None and fast.next is not None:
            slow = slow.next          # 1 step
            fast = fast.next.next     # 2 steps

            # Inside a loop, fast gains 1 node on slow every move,
            # so it must land on slow eventually.
            if slow == fast:
                return True

        # fast fell off the end: the list has an end, so no cycle.
        return False

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

export function hasCycle(head: ListNode | null): boolean {
    if (!head) return false;
    let slow = head;
    let fast: ListNode | null = head;

    // fast moves 2 steps, so check fast AND fast.next before moving it.
    while (fast !== null && fast.next !== null) {
        slow = slow.next!;        // 1 step
        fast = fast.next.next;   // 2 steps

        // Inside a loop, fast gains 1 node on slow every move,
        // so it must land on slow eventually.
        if (slow === fast) return true;
    }
    // fast fell off the end: the list has an end, so no cycle.
    return false;
}

Complexity

Time O(N)Space O(1)

Without a cycle, fast reaches the end in about n/2 moves. With a cycle, slow enters the loop within n moves, and fast catches it in less than one more lap. Only two pointers are stored.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Hash set of node pointers; seeing a node twice means a cycle	O(N)	O(N)
Optimal	slow moves 1, fast moves 2; they meet only if there is a cycle	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“determine if the list has a cycle”We only need yes/no, not where the loop is → two pointers can answer it.
“linked list, follow next”Each node has exactly one next, so the walk is a path that either ends or bends into one loop (a "ρ" shape).
“O(1) memory follow-up”No visited set → let a fast and a slow pointer find the repeat for us.

one next per node+does the walk repeat?+O(1) memory→Fast & Slow pointers — cycle detection (Floyd)

This is the anchor of the cycle sub-pattern: the plainest form of Floyd, where we only check whether they meet. The later questions reuse the same meeting: Happy Number runs it on numbers instead of nodes, Find Length of Loop walks once round from the meeting node, and Linked List Cycle II adds a second phase to find where the loop starts.

Don't make this mistake

Remembering values instead of nodes

✗ unordered_set<int> seen; if (seen.count(cur->val)) return true; seen.insert(cur->val);

✓ unordered_set<ListNode*> seen; if (seen.count(cur)) return true; seen.insert(cur);

Different nodes can hold the same value. On [7, 7, 7] with no cycle, a value set sees 7 twice and wrongly says "cycle". A cycle means the same node comes back, so store the pointer.

Checking fast->next without checking fast

✗ while (fast->next != nullptr && fast->next->next != nullptr)

✓ while (fast != nullptr && fast->next != nullptr)

For an empty list head is null, so fast->next crashes straight away. Always check fast before you read fast->next. The order matters: && stops at the first false part.

Checking slow == fast before moving

✗ while (fast && fast->next) { if (slow == fast) return true; slow = slow->next; fast = fast->next->next; }

Both start at head, so they are equal before the first move and this returns true for every list with 2+ nodes. Move first, then compare.

Treating it as "just walk until null"

✗ while (cur) cur = cur->next; return false;

This is the pattern-confusion trap: a normal list walk assumes the list ends. With a cycle it never reaches null and loops forever. Whenever a walk might repeat, you need either a visited set or a second, faster pointer to detect it.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Fast & Slow translate into production architectures and low-level memory mechanics.

LLD Architecture