Linked List Interview Questions: Reversals, Cycles, and the Hare That Catches Itself

Ask any CS student to describe a linked list and they'll nail it in fifteen seconds. Nodes, pointers, null at the end. Dead simple. Then ask them to reverse one in a live interview, with a clock running, and suddenly that confidence evaporates somewhere around step two.

Linked lists are not hard. They reward mechanical precision. One misplaced pointer assignment and you've either lost the rest of your list or created an infinite loop. Interviewers use them to watch how you think under pressure: do you track mutable state carefully? Can you prove your approach is correct instead of just hoping it works?

This post goes deep. Memory layout, pointer mechanics, the iterative reversal trick, Floyd's cycle detection with the full mathematical proof, and the pattern recognition that lets you spot a linked list problem from the first sentence of the prompt.

Every node needs a predecessor. Every single one.

What It Is

A singly linked list is a sequence of nodes where each node holds a value and a pointer to the next. The list itself is just a reference to the head node. The last node's next pointer is null (or None, or nil, depending on your language).

Mental model: a treasure hunt where each clue tells you where the next one is, but you can only ever move forward. Lose any clue and the rest of the treasure is gone forever.

You reach for a linked list when you need cheap prepend, cheap delete-at-known-position, and you can live without random access.

How It Works Internally

Node Structure

Every node is two fields. That is it.

┌─────────────┬───────────┐
│    value    │   next    │
│  (4 bytes)  │ (8 bytes) │
└─────────────┴───────────┘

Twelve bytes of actual data, sixteen with alignment padding. You're paying pointer tax on every single element.

On a 64-bit system, a pointer is 8 bytes. An int is typically 4 bytes. So a node holding a single integer carries 12 bytes of data but occupies at least 16 bytes due to alignment padding. The pointer overhead is real: for small values, the pointer can double or triple the per-element memory cost compared to a plain array.

Memory Layout

This is the part textbooks gloss over. And honestly, it's the part that explains why linked lists have a reputation that doesn't match their Big-O.

head
 │
 ▼
┌────────────┐     ┌────────────┐     ┌────────────┐
│  val: 1    │     │  val: 2    │     │  val: 3    │
│ next: ─────┼────►│ next: ─────┼────►│ next: null │
└────────────┘     └────────────┘     └────────────┘
  0x7f3c2a10         0x7f3c8b40         0x7f3c1d90

Nodes scattered across the heap. Your CPU has to fetch each one from a potentially different cache line.

Notice the addresses. They are not sequential. Each node is heap-allocated independently, so nodes end up scattered across memory. When you traverse the list, the CPU fetches each node from a potentially different cache line. Traversing a linked list of n elements can trigger n separate cache misses, while an array traversal hits one cache line every ~16 integers.

Cache misses cost around 200 clock cycles each. That adds up embarrassingly fast. This is why, in practice, a Vec or slice often beats a linked list even for workloads where linked lists have theoretically better Big-O complexity. Your Big-O doesn't account for the hardware weeping quietly in the background.

The Head Pointer

The list is nothing but a reference to the first node. Lose that reference and you cannot reach any node. The garbage collector (or you, in C) has to deal with the orphaned memory.

A common optimization is to maintain a tail pointer alongside head. Without it, appending to the end requires traversing the entire list (O(n)). With it, append becomes O(1). Many interview problems give you just head to force you to think about traversal.

The Sentinel (Dummy Head) Trick

Before writing any linked list code in an interview, consider this: add a dummy node before the real head.

dummy → node1 → node2 → node3 → null

The dummy node holds no meaningful data. Its only job is to make sure every real node has a predecessor. This kills the special case for head deletion and head insertion. Code that handles position i in the middle now handles position 0 identically. Fewer if head is None checks, fewer off-by-one bugs, cleaner code under pressure.

The dummy head is functionally useless and structurally invaluable. Kind of like that one comment everyone leaves in the code that turns out to be load-bearing.

Core Operations

Why Each Bound Holds

Prepend is O(1) because you allocate one node, point its next to the current head, then update head. No traversal, no loop.

Delete at head is O(1) for the same reason in reverse: save head.next, release the old head node, update head. Done.

Delete by value is O(n) because you need to find the node whose next points to the target. In a singly linked list you cannot reach a node's predecessor from the node itself (no back-pointer), so you walk from the head. Once you have the predecessor in hand, the actual deletion is O(1): predecessor.next = predecessor.next.next.

Search is O(n) in the worst case because there is no index, no hash, and the data is not necessarily sorted. You scan from head to tail.

Reverse is O(n) time, O(1) space using the iterative three-pointer approach. The recursive approach is also O(n) time but uses O(n) space on the call stack, one frame per node. This distinction matters and interviewers will ask.

In-Place Reversal

This is the operation that shows up most often in interviews. The naive instinct is to collect all values into an array and write them back. That works, but it uses O(n) space. Interviewers know this trick. They will ask for O(1). The optimal approach needs only three pointers.

prev    curr    next
null  → [1] → [2] → [3] → null

At each step:

1. Save curr.next as next_node
2. Flip curr.next to point at prev
3. Advance prev to curr
4. Advance curr to next_node

Step by step through a three-node list:

Step 0: prev=null, curr=1, next=?
  null ← [1]  [2] → [3] → null

Step 1: prev=1, curr=2, next=?
  null ← [1] ← [2]  [3] → null

Step 2: prev=2, curr=3, next=?
  null ← [1] ← [2] ← [3]

Step 3: curr=null, return prev (which is 3)
  3 → 2 → 1 → null

Orange = prev, blue = curr. Each step flips one arrow. Don't blink.

The key insight: you must save curr.next before you overwrite it. Miss that one line and you lose the rest of the list permanently, into the void, unreachable and unrecoverable. This is exactly the trap interviewers are watching for.

def reverse(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next   # save before overwriting
        curr.next = prev        # flip the pointer
        prev = curr             # advance prev
        curr = next_node        # advance curr
    return prev                 # new head

Fast and Slow Pointers

Once you have two pointers walking a linked list at different speeds, you can solve a surprising range of problems with O(1) extra space.

Finding the Middle

Move slow one step at a time, fast two steps. When fast reaches the end, slow is at the middle.

[1] → [2] → [3] → [4] → [5] → null

Start: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5  ← fast.next is null, stop
Middle = node 3

For even-length lists, this gives you the "upper middle" (the second of the two center nodes). If you need the lower middle, adjust the termination condition to fast.next is not None and fast.next.next is not None.

Cycle Detection (Floyd's Algorithm)

The tortoise and hare. Move slow one step, fast two steps. If there is a cycle, they will meet inside it. If fast reaches null, there is no cycle.

[1] → [2] → [3] → [4] → [5]
                    ▲         │
                    └─────────┘

The hare is faster but stuck going in circles. Eventually the tortoise catches up. The math here is genuinely satisfying.

Why they must meet: once both pointers are inside the cycle, the gap between them shrinks by exactly one step per iteration. Fast moves 2, slow moves 1, relative gain = 1 per round. That gap eventually hits zero modulo the cycle length. They land on the same node. Every time.

Finding the Cycle Entry Point

This is the harder variant and the one where most people stare at the board blankly for thirty seconds. Once you detect a cycle (slow and fast have met), reset one pointer to head and leave the other at the meeting point. Move both one step at a time. Where they meet again is the cycle's start.

The fact that this works feels like magic until you work through the proof. Then it still feels like magic, but you can explain it.

Why this works. Define:

• F = steps from head to cycle start
• a = steps from cycle start to the meeting point (inside the cycle)
• C = cycle length

When slow and fast meet:

• slow has traveled: F + a
• fast has traveled: F + a + k*C (fast lapped the cycle k extra times)
• fast travels 2x slow: F + a + k*C = 2(F + a)
• Solving: k*C = F + a, therefore F = k*C - a

After the reset, pointer1 starts at head and needs F steps to reach the cycle start. Pointer2 is at the meeting point, a steps into the cycle. From the meeting point, k*C - a more steps forward around the cycle lands exactly at the cycle start (it's k full loops minus a steps of backtracking, which is the same as moving forward to the start). So both pointers arrive at the cycle start simultaneously after F steps.

Cycle entry finding:
Reset p1 to head. p2 stays at meeting point.
Move both 1 step at a time.
They meet at the cycle start.

The proof is three lines of algebra. Walk through it once and you will never forget it.

Implementations

from __future__ import annotations
from typing import Optional

class Node:
    def __init__(self, value: int):
        self.value = value
        self.next: Optional[Node] = None

class SinglyLinkedList:
    def __init__(self):
        self.head: Optional[Node] = None

    def prepend(self, value: int) -> None:
        node = Node(value)
        node.next = self.head
        self.head = node

    def append(self, value: int) -> None:
        node = Node(value)
        if not self.head:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node

    def delete(self, value: int) -> bool:
        dummy = Node(0)
        dummy.next = self.head
        prev = dummy
        while prev.next:
            if prev.next.value == value:
                prev.next = prev.next.next
                self.head = dummy.next
                return True
            prev = prev.next
        return False

    def search(self, value: int) -> Optional[Node]:
        current = self.head
        while current:
            if current.value == value:
                return current
            current = current.next
        return None

    def reverse(self) -> None:
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

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

    def cycle_start(self) -> Optional[Node]:
        slow = self.head
        fast = self.head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                pointer = self.head
                while pointer is not slow:
                    pointer = pointer.next
                    slow = slow.next
                return pointer
        return None

What Problems It Solves

The singly linked list shows up when you need:

Efficient front insertion and deletion. If your workload is predominantly adding and removing from the front of a collection, a linked list gives you O(1) for both. Arrays pay O(n) to shift elements on every front insertion.

Dynamic-size collections with unpredictable growth. Arrays require contiguous memory. A linked list node can live anywhere on the heap, so you never need to reallocate-and-copy as the collection grows.

Implementing other data structures. Stacks, queues, and adjacency lists in graphs are all naturally expressed as linked lists. Hash table chaining (each bucket is a linked list of colliding entries) is another classic application.

LRU cache backing. The most common LRU cache implementation pairs a hash map with a doubly linked list. The linked list orders nodes by recency; the map provides O(1) lookup. Eviction is O(1): just remove the tail. Promotion on cache hit is O(1): remove the node from its position and reattach it at the head.

OS and runtime internals. The Linux kernel uses linked lists pervasively for process lists, memory descriptors, and file system structures. The kernel's implementation is notable: instead of embedding data in the node, it embeds the node (list_head) in the data struct, then uses container_of to recover the outer struct from the node pointer.

Recognizing Linked List Interview Patterns

Half the battle in an interview is recognizing that the problem in front of you wants a linked list technique at all. The prompt often won't say "linked list." It'll just describe a scenario that screams it.

Signals that a problem wants linked list technique, even when the prompt never says "linked list":

• You are given a head node and asked to modify the structure without extra data structures
• The problem says "in-place" and "O(1) space" in the same breath
• You need to find the middle, detect a cycle, or find the kth element from the end
• You need to merge or partition based on a condition
• The problem involves a "runner" technique where two pointers advance at different rates

Worked Example 1: Palindrome Check

Problem: Given a singly linked list, determine whether it is a palindrome. O(n) time, O(1) extra space.

Why a linked list technique fits: You cannot index from both ends like you can with an array. The O(1) space constraint rules out copying values into an array or stack. You have to work with the structure itself, which means reaching for patterns you just learned.

Approach:

1. Use fast/slow pointers to find the middle.
2. Reverse the second half in-place (the in-place reversal pattern).
3. Compare the first half and the reversed second half node by node.
4. Optionally restore the list by reversing the second half again.

def is_palindrome(head):
    if not head or not head.next:
        return True

    # find middle
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # reverse second half
    second_half = slow.next
    prev = None
    current = second_half
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    reversed_second = prev

    # compare
    pointer1 = head
    pointer2 = reversed_second
    result = True
    while pointer2:
        if pointer1.value != pointer2.value:
            result = False
            break
        pointer1 = pointer1.next
        pointer2 = pointer2.next
    return result

Two patterns in one problem: fast/slow for the middle, in-place reversal for the comparison. This kind of pattern composition is exactly what hard interviews are testing. If you can explain why each piece is there, you're not just solving it, you're narrating it, which is what separates a pass from a hire.

Worked Example 2: Remove Nth Node From End

Problem: Remove the nth node from the end of the list in one pass. O(n) time, O(1) space.

Why a linked list technique fits: "From the end" sounds like you need to know the length first, which costs a second pass. The "one pass" constraint is the hint. One pass with what? Two pointers.

Approach: Use two pointers with a gap of n between them. When the leading pointer reaches the end, the trailing pointer is at the node just before the one to delete.

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = dummy
    slow = dummy

    # advance fast n+1 steps to create a gap of n
    for _ in range(n + 1):
        fast = fast.next

    # move both until fast reaches the end
    while fast:
        slow = slow.next
        fast = fast.next

    # slow is now the predecessor of the node to remove
    slow.next = slow.next.next
    return dummy.next

The dummy head is pulling its weight here. When n equals the list length, slow lands on the dummy, which makes removing the real head just dummy.next = dummy.next.next. Without the dummy you need a special case. You always need a special case. That's why you add the dummy.

Recap

• A node is value plus a next pointer. The list is just the head pointer. Lose the head pointer, lose everything.
• Nodes are heap-allocated and scattered in memory. Cache misses are the price you pay for structural flexibility. The CPU is not impressed by your O(1) inserts.
• Prepend and delete-at-head are O(1). Everything else requires traversal: O(n).
• The dummy head node eliminates boundary special cases. Use it habitually, not just when you remember it.
• In-place reversal needs exactly three pointers: prev, curr, next. Save next before overwriting curr.next. That is the only line that can end your list.
• The iterative reversal is O(1) space. The recursive version is O(n) call stack. Know both; use the iterative in interviews.
• Fast/slow pointers detect cycles in O(n) time and O(1) space.
• When fast and slow meet inside a cycle, reset one pointer to head and walk both one step at a time. They converge at the cycle's entry. The proof is F = kC - a.
• Recognize the signals: "in-place", "O(1) space", "nth from end", "middle", "cycle" all point at linked list pointer techniques.

Reading about linked lists and surviving a linked list question in a live interview are two very different experiences. If you want to practice explaining these techniques out loud, with a clock running and someone asking follow-ups, SpaceComplexity runs voice-based mock interviews that cover exactly this: pointer problems, in-place transformations, and the follow-up questions interviewers ask after you write the code. Try a session before your next loop.

For more on interview communication patterns that go alongside your technical skills, see You Solved the Problem. So Why No Offer? and Don't Go Silent.

Further Reading

• Linked list (Wikipedia), canonical reference covering variants, history, and implementation trade-offs
• Floyd's Cycle-Finding Algorithm (cp-algorithms.com), clean mathematical treatment of tortoise-and-hare with full proof
• std::forward_list (cppreference.com), C++ singly linked list, with complexity guarantees for every operation
• Learning Rust With Entirely Too Many Linked Lists, ownership semantics through the lens of six different linked list implementations; essential Rust reading
• Linked List Data Structure (GeeksforGeeks), broad reference with diagrams and language examples