141. Linked List Cycle (Easy)

Problem

Given head, the head of a linked list, determine if the list has a cycle. A cycle exists if any node can be reached again by continuously following next.

Example

• head = [3,2,0,-4] with tail connected to index 1 → true
• head = [1,2] with tail connected to index 0 → true
• head = [1] with no cycle → false

LeetCode 141 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, hash set of visited nodes

Walk the list, storing each node in a hash set. If you encounter a node you’ve seen, there’s a cycle.

Python

def has_cycle(head) -> bool:
    seen = set()
    cur = head
    while cur:                   # L1: walk until end or revisit
        if cur in seen:          # L2: O(1) set lookup
            return True
        seen.add(cur)            # L3: O(1) set insert
        cur = cur.next
    return False

TypeScript

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

function hasCycle(head: ListNode | null): boolean {
    const seen = new Set<ListNode>();
    let cur = head;
    while (cur) {                // L1: walk until end or revisit
        if (seen.has(cur)) return true;  // L2: O(1) set lookup
        seen.add(cur);           // L3: O(1) set insert
        cur = cur.next;
    }
    return false;
}

Swift

final class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
        var seen: Set<ObjectIdentifier> = []
        var current = head
        while let node = current {
            guard seen.insert(ObjectIdentifier(node)).inserted else { return true }
            current = node.next
        }
        return false
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list (or nodes before cycle closes).

Line	Per-call cost	Times executed	Contribution
L1 (loop)	$O(1)$	up to n	$O(n)$
L2 (set lookup)	$O(1)$	up to n	$O(n)$ ← dominates
L3 (set insert)	$O(1)$	up to n	$O(n)$

In the acyclic case all n nodes are visited; in a cyclic case we stop when we revisit the cycle entry. Either way, at most n + cycle_length iterations before returning.

Complexity

• Time: $O(n)$, driven by L2/L3.
• Space: $O(n)$.

Simple and correct but uses linear extra memory.

Approach 2: Mark-and-sweep (destructive variant)

Mutate each visited node to a sentinel value, detect on revisit. Trashes the list, not acceptable if the caller still needs it. Included only to contrast with the optimal.

Python

def has_cycle(head) -> bool:
    SENTINEL = object()              # unique marker; can't collide with real values
    cur = head
    while cur:
        if cur.val is SENTINEL:      # revisit detected
            return True
        cur.val = SENTINEL
        cur = cur.next
    return False

TypeScript

const SENTINEL = Symbol('sentinel');

function hasCycle(head: ListNode | null): boolean {
    let cur: any = head;
    while (cur) {
        if (cur.val === SENTINEL) return true;  // revisit detected
        cur.val = SENTINEL;
        cur = cur.next;
    }
    return false;
}

Swift

final class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
        var current = head
        while let node = current {
            if node.val == Int.min { return true }
            node.val = Int.min
            current = node.next
        }
        return false
    }
}

$O(n)$ time, $O(1)$ extra space, but the list is now wrecked: every visited node’s value is overwritten with the sentinel.

A non-mutating $O(1)$-space alternative is Approach 3 below.

Approach 3: Floyd’s tortoise and hare (optimal)

Two pointers: slow moves one step, fast moves two. If there’s a cycle, they’ll meet inside it; if there’s no cycle, fast reaches the end.

Python

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:      # L1: guard against end of list
        slow = slow.next           # L2: O(1) advance slow by 1
        fast = fast.next.next      # L3: O(1) advance fast by 2
        if slow is fast:           # L4: O(1) meeting check
            return True
    return False

TypeScript

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {    // L1: guard against end of list
        slow = slow!.next;         // L2: O(1) advance slow by 1
        fast = fast.next.next;     // L3: O(1) advance fast by 2
        if (slow === fast) return true;  // L4: O(1) meeting check
    }
    return false;
}

Swift

final class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if sameNode(slow, fast) { return true }
        }
        return false
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list, c = length of cycle (0 if acyclic).

Line	Per-call cost	Times executed	Contribution
L1 (guard)	$O(1)$	up to n + c	$O(n)$
L2-L3 (advance pointers)	$O(1)$	up to n + c	$O(n)$ ← dominates
L4 (meeting check)	$O(1)$	up to n + c	$O(n)$

In the acyclic case fast exits in n/2 iterations. In the cyclic case fast enters the cycle after at most n steps; once both pointers are in the cycle of length c, they meet within c more steps. Total: $O(n + c)$ = $O(n)$.

Complexity

• Time: $O(n)$. In a cycle of length c, the pointers meet within c steps of entering it (L2-L3).
• Space: $O(1)$.

Why it works

Once both pointers are inside the cycle, the gap between them decreases by 1 each step (slow advances 1, fast advances 2, relative to slow that’s a +1). Eventually the gap is 0, they meet. If there’s no cycle, fast falls off the end.

Follow-up (problem 142)

If you need the cycle start, not just existence, reset slow to head after the meet, then advance both by one step until they meet again. They meet at the cycle start. (Proof is a bit of modular arithmetic; trust the procedure.)

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_141.py and run.
# Uses Floyd's tortoise and hare (Approach 3).

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

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def _run_tests():
    # No cycle, empty
    assert has_cycle(None) == False

    # No cycle, single node
    assert has_cycle(ListNode(1)) == False

    # No cycle, multiple nodes
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n1.next = n2; n2.next = n3
    assert has_cycle(n1) == False

    # Cycle: tail connects to index 1
    a = ListNode(3)
    b = ListNode(2)
    c = ListNode(0)
    d = ListNode(-4)
    a.next = b; b.next = c; c.next = d; d.next = b  # cycle at b
    assert has_cycle(a) == True

    # Cycle: single node pointing to itself
    x = ListNode(1)
    x.next = x
    assert has_cycle(x) == True

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

// No cycle, empty
console.assert(hasCycle(null) === false);
// No cycle, single node
console.assert(hasCycle(new ListNode(1)) === false);
// No cycle, multiple nodes
const n1 = new ListNode(1); const n2 = new ListNode(2); const n3 = new ListNode(3);
n1.next = n2; n2.next = n3;
console.assert(hasCycle(n1) === false);
// Cycle: tail connects to index 1
const a = new ListNode(3); const b = new ListNode(2);
const c = new ListNode(0); const d = new ListNode(-4);
a.next = b; b.next = c; c.next = d; d.next = b;
console.assert(hasCycle(a) === true);
// Single node cycle
const x = new ListNode(1); x.next = x;
console.assert(hasCycle(x) === true);
console.log("all tests pass");

Summary

Approach	Time	Space
Hash set of visited	$O(n)$	$O(n)$
Floyd’s tortoise and hare	$O(n)$	$O(1)$

The two-pointer technique here extends to 142 (Linked List Cycle II) and 287 (Find the Duplicate Number).

Related data structures

• Linked Lists, two-pointer cycle detection; Floyd’s algorithm

Related concepts

• Cycle Detection, repeated-state tactics for finding loops in linked lists, graphs, arrays, and numeric processes.
• Fast and Slow Pointers, pointer-speed tactics for cycle detection, middle finding, and linked-list distance constraints.