Linked Lists: The Data Structure That Trips Everyone Up

Why Linked Lists Break Candidates Who Know Them

Here is a scenario that plays out in technical interviews every day:

A candidate with two years of production experience sits down to reverse a linked list. They've done it before. They know the answer. Fifteen minutes later, they're staring at a null pointer exception they can't explain, their solution produces an infinite loop on the second test case, and the interviewer has moved from curious to concerned.

Linked lists don't fail candidates because the concepts are hard. They fail candidates because pointer manipulation under pressure — keeping track of three or four variables simultaneously while explaining your reasoning out loud — is genuinely difficult if you haven't built the right mental model.

This post gives you that mental model. Not just the code templates, but the way to think about pointers so the code becomes an inevitable consequence of clear thinking rather than something you memorize and hope to recall correctly.

The Mental Model: Pointers Are Just Variables Holding Addresses

The source of most linked list bugs is treating pointers as something magical. They aren't. A pointer is a variable that holds a memory address — nothing more.

When you write current = current.next, you are changing what address the variable current holds. The node that current used to point to still exists in memory, unchanged, unless you've also changed current.next to point somewhere else.

This single insight prevents the most common linked list bug in interviews:

# THE BUG: losing a reference before you need it
def reverse_buggy(head):
    prev = None
    current = head
    while current:
        current.next = prev      # ❌ you just lost current.next
        prev = current           # now prev points to current
        current = current.next   # current.next is now prev (None)! infinite loop

# THE FIX: save the reference before overwriting it
def reverse_correct(head):
    prev = None
    current = head
    while current:
        next_node = current.next  # ✅ save before overwriting
        current.next = prev       # rewire
        prev = current            # advance prev
        current = next_node       # advance current using saved reference
    return prev

The rule: Before you overwrite any .next pointer, save where it was pointing. Every linked list bug in interviews comes from violating this rule.

Draw it out. On a whiteboard, before writing code, draw three boxes representing prev, current, and next_node. Draw arrows between them. Step through one iteration manually. The code writes itself.

The Node Structure

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

# Build a linked list from a Python list (useful for testing)
def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Convert linked list back to Python list (useful for verification)
def to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Always build these two helpers at the top of your scratch space during an interview. They let you test your solution quickly without drawing the entire linked list each time.

Technique 1: The Dummy Head

Ninety percent of linked list edge case bugs come from special-casing the head node. The dummy head pattern eliminates this entirely.

A dummy head is a sentinel node prepended to the list. It has no meaningful value. Its only purpose: to ensure that the "actual" head of the list is never a special case in your logic.

# WITHOUT dummy head: head insertion is a special case
def remove_value_messy(head, val):
    # must handle head separately
    while head and head.val == val:
        head = head.next
    current = head
    while current and current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
    return head

# WITH dummy head: uniform logic, no special cases
def remove_value_clean(head, val):
    dummy = ListNode(0)
    dummy.next = head
    current = dummy            # start at dummy, not head

    while current.next:
        if current.next.val == val:
            current.next = current.next.next   # skip the node
        else:
            current = current.next

    return dummy.next          # dummy.next is the new head

Use the dummy head whenever: you might need to delete the head node, you're building a new list by appending nodes, or you're merging two lists.

The dummy head pattern is simple and almost always correct on the first try. Candidates who skip it to "save time" end up spending ten minutes debugging edge cases they would never have encountered with the dummy.

Technique 2: Reversal

Reversal is the most-tested linked list operation. You need to be able to write it from memory in under two minutes, explain each step, and extend it to reverse sublists.

Full Reversal

def reverse_list(head):
    prev = None
    current = head

    while current:
        next_node = current.next  # save
        current.next = prev       # rewire
        prev = current            # advance
        current = next_node       # advance

    return prev   # prev is now the new head

Step through 1 → 2 → 3 → None manually:

Initial: prev=None, current=1

Iteration 1:
  next_node = 2
  1.next = None    (1 → None)
  prev = 1
  current = 2

Iteration 2:
  next_node = 3
  2.next = 1       (2 → 1 → None)
  prev = 2
  current = 3

Iteration 3:
  next_node = None
  3.next = 2       (3 → 2 → 1 → None)
  prev = 3
  current = None

Loop ends. Return prev = 3.
Result: 3 → 2 → 1 → None  ✓

Recursive Reversal

def reverse_recursive(head):
    # Base case: empty list or single node
    if not head or not head.next:
        return head

    # Reverse the rest of the list
    new_head = reverse_recursive(head.next)

    # Make head.next point back to head
    head.next.next = head
    head.next = None

    return new_head

The iterative version is preferred in interviews — it's O(1) space vs O(n) call stack for the recursive version. Know both, but reach for the iterative one.

Reverse a Sublist (Positions m to n)

This is the harder variant — reversing only a portion of the list:

def reverse_between(head, left, right):
    if not head or left == right:
        return head

    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    # Move prev to the node just before position 'left'
    for _ in range(left - 1):
        prev = prev.next

    current = prev.next   # first node of the sublist to reverse

    # Reverse right-left times
    for _ in range(right - left):
        next_node = current.next
        current.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node

    return dummy.next

Canonical Problems

• Reverse Linked List (Easy)

• Reverse Linked List II (Medium)

• Palindrome Linked List (Medium)

Technique 3: Fast & Slow Pointers

Two pointers moving at different speeds — slow advances one step per iteration, fast advances two. In a cycle-free list, fast reaches the end first. In a cyclic list, fast laps slow and they meet.

This single technique solves five different linked list problems.

Cycle Detection (Floyd's Algorithm)

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # 1 step
        fast = fast.next.next   # 2 steps

        if slow == fast:        # they met → cycle exists
            return True

    return False   # fast reached end → no cycle

Why do they always meet inside the cycle? Once both pointers enter the cycle, fast gains one node on slow per iteration. The distance between them decreases by 1 each step. It reaches 0 in at most cycle_length iterations.

Find the Start of the Cycle

def detect_cycle_start(head):
    slow = head
    fast = head

    # Phase 1: detect the cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None    # no cycle

    # Phase 2: find the entry point
    # Move one pointer to head, keep the other at meeting point.
    # Both advance one step at a time — they meet at cycle start.
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow

Why does this work? If the list has F nodes before the cycle and cycle length C, the meeting point inside the cycle is at distance C - (F % C) from the start. Moving a pointer back to head and advancing both one step at a time makes them meet exactly at the cycle entry — the math works out.

Find the Middle Node

def find_middle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow   # when fast reaches end, slow is at middle

For even-length lists, this returns the second of the two middle nodes. If the problem requires the first middle node:

def find_middle_first(head):
    slow = head
    fast = head.next   # fast starts one step ahead

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Remove the Nth Node From the End

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

    # Move fast n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next

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

    # slow is now at the node before the one to delete
    slow.next = slow.next.next

    return dummy.next

Why n+1? We want slow to stop at the node before the target (so we can delete it). Moving fast one extra step creates that gap.

Canonical Problems

• Linked List Cycle (Easy)

• Find the Duplicate Number (Medium)

• Remove Nth Node From End of List (Medium)

Technique 4: The Runner Technique

The runner technique uses two pointers separated by a fixed distance (k nodes apart) to solve problems that require looking ahead or comparing nodes at a relative offset.

# Check if linked list is a palindrome — O(n) time, O(1) space
def is_palindrome(head):
    # Step 1: find the middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: reverse the second half
    prev = None
    current = slow
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    second_half = prev

    # Step 3: compare first half with reversed second half
    first = head
    second = second_half
    result = True
    while second:
        if first.val != second.val:
            result = False
            break
        first = first.next
        second = second.next

    # Step 4 (optional): restore the list
    # reverse second_half back and reconnect to slow
    return result

This problem is the canonical test of whether you can combine multiple techniques fluently — fast/slow pointers to find the middle, reversal, then two-pointer comparison.

# Reorder list: L0 → L1 → ... → Ln-1 → Ln
# becomes:      L0 → Ln → L1 → Ln-1 → L2 → ...
def reorder_list(head):
    if not head or not head.next:
        return

    # Step 1: find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # slow is now at the end of first half

    # Step 2: reverse second half
    second = slow.next
    slow.next = None   # cut the list
    prev = None
    while second:
        next_node = second.next
        second.next = prev
        prev = second
        second = next_node
    second = prev

    # Step 3: merge two halves by interleaving
    first = head
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

Technique 5: Merging

Merging two sorted linked lists is a fundamental building block — it's the merge step in merge sort, and it appears directly in multiple interview problems.

Merge Two Sorted Lists

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Attach the remaining nodes
    current.next = l1 if l1 else l2

    return dummy.next

Why current.next = l1 if l1 else l2 works: One of the lists is exhausted, the other has remaining sorted nodes. They can be attached directly — no need to continue iterating.

Merge K Sorted Lists (Heap Approach)

import heapq

def merge_k_lists(lists):
    dummy = ListNode(0)
    current = dummy
    heap = []

    # Initialize heap with head of each list
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
            # (value, list_index, node) — list_index breaks ties

    while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

Complexity: O(n log k) where n is total nodes and k is number of lists. The heap never holds more than k elements, so each push/pop is O(log k). We do this for every node: O(n log k) total.

Canonical Problems

• Merge Two Sorted Lists (Easy)

• Merge K Sorted Lists (Hard)

• Sort List (Medium)

The 5 Questions to Ask Before Writing Code

Before touching any linked list problem, answer these five questions out loud. They force you to think through edge cases before the code is written — which is far easier than debugging them after.

Q1: Can the input be empty (head = None)? If yes, your first line should handle it: if not head: return head

Q2: Can the input be a single node? Many solutions fail on single-node inputs (especially reversal and palindrome check). Trace through manually.

Q3: Can the input have a cycle? If the problem doesn't mention cycles, assume no. But if the problem does mention cycles (or says "detect"), fast/slow pointers are the answer.

Q4: Do I need to return a new head? Some operations (reversal, deletion of head) change which node is the head. Always return dummy.next if you used a dummy, or prev if you used iterative reversal.

Q5: Do I need to handle even vs. odd length differently? Palindrome check, middle-finding, and reorder operations behave differently on even vs. odd length lists. Trace both cases manually before coding.

The Complete Decision Framework

Linked list problem received
         │
         ▼
Might need to delete/modify the head, or build a new list?
  └─ Yes → Use DUMMY HEAD from the start
         │
         ▼
Problem about CYCLE detection or finding cycle start?
  └─ Yes → FAST & SLOW POINTERS (Floyd's Algorithm)
         │
         ▼
Problem about MIDDLE of list, Nth from end, or kth element?
  └─ Yes → FAST & SLOW POINTERS (or two-pass: count then traverse)
         │
         ▼
Problem requires REVERSING all or part of the list?
  └─ Yes → ITERATIVE REVERSAL (save next before rewiring)
         │
         ▼
Problem requires PALINDROME check or REORDER operation?
  └─ Yes → COMBINE: find middle + reverse second half + compare/merge
         │
         ▼
Problem involves MERGING sorted lists?
  ├─ 2 lists → ITERATIVE MERGE with dummy head
  └─ K lists → MIN-HEAP merge

The 9 Linked List Problems Every Candidate Must Know

Problems 1–4 are the foundation. Problems 5–8 each combine two or three of the core techniques. Problem 9 extends merge to the general k-list case. That progression — simple → combined → generalized — is exactly how interviewers escalate difficulty.

Bottom Line

Linked lists test one thing more than anything else: your ability to keep a mental picture of pointer state while talking out loud and writing code simultaneously. That's a coordination challenge, not an intellectual one.

The solution is deliberate practice with the mental model, not just code memorization. Before writing any linked list solution, draw the state after each pointer move. Do this ten times with reversal alone until you can close your eyes and see the arrows changing. Then the code stops being something you recall and starts being something you derive.

The techniques in this post — dummy head, reversal, fast/slow pointers, runner, merging — cover every linked list problem you will encounter at any company. There are no exotic linked list patterns beyond these five. Master them deeply, not broadly.

🧭 What's Next in This Series

Three posts down in Chapter 2. Three more to go:

• Post 07: Stacks & Queues — the monotonic stack, deque patterns, and the BFS connection that unlocks some of the hardest Medium problems in O(n)