Skip to content

Volume ITechnology

4.9.7 — Linked List Cycle ​

LeetCode 141 · Easy · ★ Blind 75

The problem ​

You are given the head of a linked list. Return true if the list has a cycle, and false otherwise. A list has a cycle when following next pointers over and over eventually brings you back to a node you have already visited, so the walk never ends.

3 → 2 → 0 → -4
    ↑         |
    └─────────┘        →  true   (-4 points back to 2)

1 → 2 → null           →  false  (the walk reaches the end)

The list has up to 10,000 nodes. The follow-up asks for O(1) extra memory.

What the problem is really asking ​

If the list has no cycle, walking it eventually reaches null. If it has a cycle, the walk goes round the loop forever. You cannot just walk and wait, because you would never know whether the end is near or whether you are going round in circles.

So the real question is: how do you notice that you have come back to a node you visited before?

The brute force, and where it wastes memory ​

Remember every node you have visited, in a set. If you reach a node that is already in the set, you have gone round a loop.

python
def hasCycle(head):
    seen = set()
    node = head
    while node:
        if node in seen:          # back to a node we have visited
            return True
        seen.add(node)
        node = node.next
    return False                  # reached the end

This is O(n) time and correct. It is a perfectly good first answer.

The cost in one sentence: it stores every node in a set, which is O(n) memory, when two moving pointers can detect the loop with no memory at all.

The idea ​

Use two pointers that move at different speeds. This is Floyd's cycle detection, often called the tortoise and the hare.

  • slow moves one node per step.
  • fast moves two nodes per step.

If there is no cycle, fast reaches the end of the list and we are done. If there is a cycle, both pointers end up going round the loop. Then fast must eventually land on the same node as slow.

Think of two runners on a circular track, one running twice as fast as the other. The fast runner will eventually come up behind the slow one and draw level.

Why they must meet ​

Once both pointers are inside the loop, look at the gap: how many steps fast would need to walk forward round the loop to reach slow.

On every step, slow moves forward 1 and fast moves forward 2. So fast gains exactly 1 step on slow. The gap gets smaller by exactly one each step.

A number that goes down by exactly 1 each time, starting from some whole number, must eventually hit 0. When the gap is 0, the two pointers are on the same node.

The step size of 1 is what makes this certain. Suppose fast moved three nodes per step. Then it would gain 2 per step, and the gap would shrink by 2 each time. If the gap were odd, it would go 3, 1, −1, jumping straight past 0. The pointers could pass each other without ever landing on the same node. Gaining exactly one per step means no number is ever skipped.

That is the whole proof, and it is short enough to say out loud in an interview.

The solution ​

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

        while fast and fast.next:              # (2)
            slow = slow.next                   # (3)
            fast = fast.next.next              # (4)
            if slow is fast:                   # (5)
                return True

        return False                           # (6)
ts
function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;                // (1)

  while (fast && fast.next) {                  // (2)
    slow = slow!.next;                         // (3)
    fast = fast.next.next;                     // (4)
    if (slow === fast) return true;            // (5)
  }

  return false;                                // (6)
}

Line by line ​

(1) Both pointers start at the head.

(2) Can fast take two more steps? fast is about to step onto fast.next and then fast.next.next. So both fast and fast.next must exist. Checking only fast would crash when fast.next is None. If either is missing, the list has an end, so there is no cycle.

(3) slow moves one step.

(4) fast moves two steps.

(5) Are they on the same node? We compare identity: is in Python and === in TypeScript, which ask "is this the very same node object?" We do not compare values, because two different nodes can hold the same value.

We check after moving. Both pointers start on the head, so checking before moving would report a cycle at once on every list.

(6) fast reached the end, so the list has no cycle.

Trace ​

Take 3 → 2 → 0 → -4, where −4 points back to 2. Call the nodes by their values.

StepslowfastSame node?
start33(not checked)
120no
202 (−4, then back to 2)no
3−4−4 (0, then −4)yes → true

Now 1 → 2 → null. Step 1 moves slow to 2 and fast to null (1 → 2 → null). The loop condition fails, and we return false.

Complexity, derived ​

Time. Before the loop is reached, slow takes at most n steps to walk the part of the list before the cycle. Once both are inside, the gap is less than the length of the loop, which is at most n, and it shrinks by 1 per step. So that part also takes at most n steps. In total, at most about 2n steps, which is O(n).

Space. Two pointers. So the extra memory is O(1).

Edge cases ​

  • Empty list. fast is None, the loop never runs, and the answer is false.
  • One node pointing to itself. Step 1: slow moves to the node, fast moves two steps and lands on the same node. They meet. true.
  • One node with no cycle. fast.next is None, so false.
  • The cycle is the whole list. Both are inside from the start. They meet within n steps.

Finding where the cycle starts ​

Linked List Cycle II (LeetCode 142) asks for the node where the cycle begins. A small piece of arithmetic gives it.

Name three distances.

  • a: from the head to the start of the cycle.
  • b: from the start of the cycle to the node where slow and fast meet.
  • c: from the meeting node the rest of the way round, back to the start of the cycle. So the loop's length is b + c.

When they meet, slow has walked a + b. fast has walked twice as far, 2(a + b). But fast has also walked the same path as slow, plus some whole number of extra laps, call it k laps:

2(a + b) = a + b + k(b + c)

Take a + b away from both sides:

a + b = k(b + c)

Now take b away from both sides:

a = k(b + c) - b = (k - 1)(b + c) + c

Read that last line in words. The distance from the head to the cycle's start equals the distance from the meeting point to the cycle's start (c), plus some whole number of full laps. Full laps bring you back to where you began, so they do not change where you end up.

So: put one pointer back at the head, leave the other at the meeting point, and move both one step at a time. After a steps, the first one reaches the cycle's start. The second one has walked c plus some full laps, which also lands on the cycle's start. They meet there.

python
def detectCycle(self, head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                     # they met inside the cycle
            slow = head                      # restart one pointer at the head
            while slow is not fast:          # both now move one step at a time
                slow, fast = slow.next, fast.next
            return slow                      # the start of the cycle
    return None

Variations you will meet ​

This technique is not really about linked lists. It works on any process where each state has exactly one next state, and it detects that the process eventually repeats.

  • Find the Duplicate Number. Treat each array value as a pointer to another position. The repeated value becomes the start of a cycle. That is the next page, 4.9.8, and it is the most surprising use of this idea.
  • Happy Number. Replace a number by the sum of the squares of its digits, again and again. Either you reach 1, or you go round a cycle. See 4.28.4.

The general lesson: when a process has exactly one next state, two pointers at different speeds detect repetition using no extra memory.

What the interviewer will push on ​

"Prove the pointers must meet." The gap shrinks by exactly one per step, so it cannot skip over zero.

"Why does fast move two and not three?" Gaining two per step can jump past zero without landing on it.

"Find where the cycle starts." Derive the algebra above. Deriving it, not reciting it, is what they are checking.

"What about the set version?" O(n) memory, simpler, and completely fine to give first.

One thing to volunteer: name the method, Floyd's cycle detection, and say it works on any process with one next state, not just lists. That leads straight into the next problem.

Next: 4.9.8 Find the Duplicate Number. An array problem that turns out to be this one in disguise.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet