📖 7 min read
Last updated on

Linked List Cycle — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer asks: “Determine whether a linked list contains a cycle.” You reach for a hash set and solve it in O(n) space. Then the follow-up: “Can you do it in O(1) space?” Now you need Floyd’s algorithm, and more importantly, you need to explain why two pointers at different speeds are guaranteed to meet inside a cycle without skipping past each other.

This walkthrough covers both approaches, the mathematical intuition behind Floyd’s algorithm, every edge case, and the follow-up questions interviewers always ask.

The Problem

Given the head of a linked list, determine if the list contains a cycle. A cycle exists if some node can be reached again by continuously following the next pointer. Return true if there is a cycle, false otherwise. (LeetCode #141)

Example

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

Output true

The tail node (-4) points back to index 1 (value 2), creating a cycle: 3 → 2 → 0 → -4 → 2 → .... Note that pos is not a parameter to your function.

Linked list with nodes 3→2→0→-4 where the tail node -4 points back to node 2, forming a cycle. Head is at node 3, cycle entry is at node 2.

The teal arrow shows the cycle: after reaching -4, the next pointer loops back to 2 instead of terminating. A second example: head = [1,2], pos = -1 returns false because the list terminates at None.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Linked List Cycle is a direct test of fast/slow pointer intuition. The hash set solution is the baseline; the real question is whether you can reach O(1) space and justify why it works.

SkillWhat Interviewers Observe
Hash set recognitionDo you identify the O(n) space solution as a natural starting point?
Two-pointer (Floyd’s) insightDo you independently derive the fast/slow pointer approach?
Invariant justificationCan you explain why fast and slow are guaranteed to meet inside a cycle?
Termination conditionDo you correctly check fast and fast.next for None before advancing?
Edge case handlingDo you handle empty lists, single nodes, and self-loops?
Follow-up readinessCan you find the cycle’s start node (LeetCode #142)?

Step 1: Clarifying Questions

  1. Should I return a boolean, or identify where the cycle starts? Just a boolean. LeetCode #142 asks for the entry node, a meaningfully harder follow-up.

  2. Can the list be empty? Yes. An empty list has no cycle.

  3. Can a single node point to itself? Yes. node.next = node is a valid cycle. Trace it mentally: fast reaches node.next.next = node, equaling slow on the first iteration.

  4. Are values guaranteed unique? No. The hash set stores node references, not values. Two nodes with the same value are distinct objects.

Step 2: A First (Non-Optimal) Idea

Use a hash set to track visited nodes. If you encounter a node already in the set, a cycle exists. If you reach None, no cycle.

def hasCycle(head):
    visited = set()
    current = head

    while current is not None:
        if current in visited:
            return True     # Seen this node before — cycle detected
        visited.add(current)
        current = current.next

    return False  # Reached the end — no cycle

This is O(n) time and O(n) space. Present it first, then name the limitation: “This works but uses O(n) extra space. For O(1) space, I need a different technique.”

ApproachTimeSpace
Hash setO(n)O(n)
Floyd’s two-pointerO(n)O(1)

Step 3: The Key Insight

If a cycle exists, a faster pointer will eventually lap a slower pointer inside the loop. Fast gains exactly one step per iteration, so the gap closes by one each time, guaranteeing collision.

Imagine two runners on a circular track, one running twice as fast. No matter the loop size, the faster runner eventually catches the slower one.

  • No cycle: fast reaches None first. Return false.
  • Cycle exists: Both enter the cycle. Fast gains one step per iteration. Starting from any gap d, after d iterations the gap is zero. They meet.

They can’t skip past each other because the gap decreases by exactly one, not by two or more. A gap of 1 becomes 0 on the next step.

Step 4: Optimal Strategy (Floyd’s Algorithm)

  1. If head is None or head.next is None, return False.
  2. Initialize slow = head and fast = head.
  3. While fast is not None and fast.next is not None:
    • slow = slow.next (one step).
    • fast = fast.next.next (two steps).
    • If slow == fast, return True.
  4. Return False.

Python Implementation

Hash Set (O(n) space, intuitive)

def hasCycle(head: ListNode) -> bool:
    visited = set()
    current = head

    while current is not None:
        if current in visited:
            return True       # Cycle confirmed
        visited.add(current)
        current = current.next

    return False  # Reached None — no cycle

Floyd’s Tortoise and Hare (O(1) space, optimal)

def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False  # Empty list or single node without self-loop

    slow = head        # Moves 1 step at a time
    fast = head        # Moves 2 steps at a time

    while fast is not None and fast.next is not None:
        slow = slow.next          # One step
        fast = fast.next.next     # Two steps

        if slow == fast:
            return True   # Pointers met — cycle detected

    return False  # fast hit None — list terminates

Key implementation notes:

  • fast is not None and fast.next is not None guards two-step advancement. Check fast first (short-circuit), then fast.next. Reversing the order or omitting either check causes AttributeError.
  • Both pointers start at head. They diverge on the first iteration. Starting fast = head.next also works but requires adjusting the loop.
  • Pointer equality compares references, not values. Two nodes with the same val are distinct objects.
  • The hash set stores node objects, not values. visited.add(current) adds the reference.

Time & Space Complexity

ApproachTimeSpace
Hash SetO(n)O(n)
Floyd’s Two-PointerO(n)O(1)

Time (Floyd’s): Without a cycle, fast reaches the end in O(n/2) steps. With a cycle, after both enter the loop, they meet within at most c iterations (cycle length). Since c <= n, total is O(n).

Space (Floyd’s): Two pointer variables regardless of list size. True O(1).

Common Interview Mistakes

  1. Forgetting to check fast.next before advancing. If fast is the last node, fast.next.next raises AttributeError. The most common bug.

  2. Using node values instead of references in the hash set. Storing current.val instead of current gives false positives when values repeat.

  3. Not explaining why pointers are guaranteed to meet. Saying “fast catches slow” without justifying why is hand-waving. The real explanation: fast gains exactly one step per iteration, so the gap closes by one deterministically.

  4. Not presenting the hash set solution first. Jumping to Floyd’s without establishing the O(n) space baseline makes the optimization appear unjustified.

  5. Not mentioning the follow-up (finding cycle start). Most interviewers will ask about LeetCode #142. Having a prepared answer (“reset one pointer to head, advance both one step, they meet at cycle entry”) signals depth.

What a Strong Candidate Sounds Like

“My first instinct is a hash set: traverse the list, track visited nodes. If I see the same node twice, there’s a cycle. O(n) time and space.

For O(1) space, I use Floyd’s tortoise and hare. Two pointers at head: slow moves one step, fast moves two. If no cycle, fast reaches None. If there’s a cycle, fast gains one step per iteration on slow. The gap closes by exactly one each time, so they’re guaranteed to meet. O(n) time, O(1) space.

If the follow-up is finding the cycle entry, that’s LeetCode #142.”

Example Interview Dialogue

Interviewer: Determine whether a linked list contains a cycle.

Candidate: Quick clarification: I return a boolean, not the cycle entry node?

Interviewer: Correct.

Candidate: Hash set first: track visited node references. If I see a node twice, return true. If I hit None, return false. O(n) time and space. For O(1) space, I’ll use Floyd’s algorithm.

Interviewer: Please do.

Candidate: Two pointers from head. Slow moves one step, fast moves two. If no cycle, fast exits first. With a cycle, fast gains one step per iteration on slow. The gap closes deterministically. They meet within c steps where c is cycle length.

Interviewer: Why can’t fast skip over slow?

Candidate: The gap decreases by exactly one each iteration. It goes from d to d-1 to d-2, down to 1, then 0. It never jumps from 2 to 0 because fast moves exactly two steps and slow moves exactly one, netting one step gained.

Interviewer: How would you find the cycle start?

Candidate: After slow and fast meet, reset slow to head. Advance both one step at a time. They meet at the cycle entry. The math: the distance from head to cycle entry equals the distance from meeting point to cycle entry (modulo cycle length).

Linked List Cycle is the entry point for the fast/slow pointer pattern:

Practice This in a Mock Interview

The fast/slow pointer pattern has a specific failure mode under pressure: candidates who memorized the approach stumble when asked why the pointers are guaranteed to meet, and stall when asked about the cycle entry follow-up.

The difference between a candidate who knows Floyd’s algorithm and one who truly understands it comes out in exactly those moments. The only way to build that depth is to practice explaining the invariant out loud and field follow-up questions in real time.

Start a mock interview for Linked List Cycle on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →