Skip to content

071 — Linked List Cycle

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

71 — Linked List Cycle

LeetCode 141 · Easy. Given the head of a linked list, determine whether the list has a cycle in it — that is, whether some node's next pointer eventually loops back to a node already visited.

🍽️ Intuition

Picture two runners starting at the same point on a track — one jogging at normal pace, the other sprinting at double speed. If the track is a straight line with a finish line at the end, the sprinter just reaches the end first, no drama. But if the track secretly loops back on itself, the sprinter never finds a finish line — instead, having covered ground twice as fast, they eventually come up behind the jogger and lap them. That collision is unmistakable proof the track loops. You never needed a map of the track or a list of every place you'd already been — just two runners at different speeds and the question "did the fast one ever run into the slow one again?"

🚩 Pattern-Recognition Cue

"Has a cycle" or "loop" in a linked-list problem is the single most direct trigger for Fast and Slow Pointers in this entire curriculum — this is the canonical example the pattern is named for. No stretch, no alternate framing needed: whenever you need to detect whether a linked structure loops back on itself without extra memory, race two pointers at speeds 1 and 2.

🐢 Brute Force

Track every node you've visited in a hash set (using ObjectIdentifier since ListNode isn't Hashable); if you ever revisit a node, a cycle exists.

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) { self.val = val }
}

func hasCycleBruteForce(_ head: ListNode?) -> Bool {
    var visited = Set<ObjectIdentifier>()
    var curr = head
    while let node = curr {
        let id = ObjectIdentifier(node)
        if visited.contains(id) {
            return true
        }
        visited.insert(id)
        curr = node.next
    }
    return false
}

// smoke test: 1 -> 2 -> 3 -> back to 2 (cycle)
let a1 = ListNode(1); let a2 = ListNode(2); let a3 = ListNode(3)
a1.next = a2; a2.next = a3; a3.next = a2
print(hasCycleBruteForce(a1))   // true

// smoke test: 1 -> 2 -> nil (no cycle)
let b1 = ListNode(1); let b2 = ListNode(2)
b1.next = b2
print(hasCycleBruteForce(b1))   // false

Big-O: O(n) time — visits each node at most once before either finding a repeat or running out of list. O(n) extra space for the visited set.

🚀 Optimal

Race a slow pointer (1 step) against a fast pointer (2 steps); if they ever meet, there's a cycle, and if fast falls off the end, there isn't.

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 slow === fast {
            return true
        }
    }

    return false
}

// smoke test: 1 -> 2 -> 3 -> back to 2 (cycle)
let c1 = ListNode(1); let c2 = ListNode(2); let c3 = ListNode(3)
c1.next = c2; c2.next = c3; c3.next = c2
print(hasCycle(c1))   // true

// smoke test: 1 -> 2 -> nil (no cycle)
let d1 = ListNode(1); let d2 = ListNode(2)
d1.next = d2
print(hasCycle(d1))   // false

// smoke test: single node with no cycle
print(hasCycle(ListNode(1)))   // false

Big-O: O(n) time — once both pointers are inside a cycle, fast gains exactly one node on slow per step, so they meet within at most n steps; with no cycle, fast reaches nil in at most n/2 steps. O(1) extra space — just two pointer variables, no matter how long the list is.

🔑 The Key Insight

Detecting a cycle only requires answering "will I ever see this node again?" — and a hash set answers that by brute-force remembering everywhere you've been, which costs O(n) space. Fast and Slow Pointers answers the same question without remembering anything at all: if there's no cycle, the faster pointer simply reaches the natural end (nil) first, since it's covering the finite list twice as fast. If there is a cycle, both pointers eventually enter it and can never escape — and because the fast pointer closes the gap between them by exactly one node every step (moving 2 vs. 1), and a cycle is a finite loop, that gap is mathematically guaranteed to hit exactly zero rather than skip past it. The meeting itself, not a memory of prior positions, is the proof — which is what collapses O(n) space down to O(1).

🔗 Related Chapters

  • Linked Lists — the underlying data structure; a cycle means some node's next pointer breaks the "eventually reaches nil" guarantee a normal list has.
  • Fast and Slow Pointers — this problem is that chapter's canonical worked example; no reframing needed, the fast/slow race is the solution.
  • Hash Maps & Hash Sets — the data structure behind the brute force's O(n)-space "have I seen this node before" check.

🧸 Memory Sentence

Linked List Cycle is two runners at different speeds on a track — if it loops, the fast one always laps the slow one, and that catch-up moment proves the loop exists without ever mapping the track.

✅ Check Your Understanding

Explain why the loop guard is written while fast != nil && fast?.next != nil rather than just while fast != nil. What would go wrong — specifically, what would crash or misbehave — if the guard only checked fast != nil and the code proceeded straight to fast = fast?.next?.next?

⬅️ Previous: Add Two Numbers · Next: Find the Duplicate Number ➡️

Clone this wiki locally