Linked list pointer patterns

You are ten minutes into a coding round. You have said "I'll reverse the list in place," and now there are three variables on the board and one arrow pointing the wrong way. Linked list questions take a sentence to state and one misplaced assignment to break, so the interviewer watches how you move pointers: whether every node stays reachable, and whether the first node and the empty list get handled without a pile of special cases. After this lesson you can write a node class in a minute, insert and delete without a head special case, reverse a list in place, find the middle with two pointers and say what recursion on a list really costs.

Singly or doubly linked

A linked list is a chain of nodes. Each node holds a value and a reference to the next node. The first node is the head, the last is the tail, and the tail's next is None. In Python a "pointer" is just an attribute that refers to another object, so a.next = b points a at b. A singly linked list has only next. A doubly linked list adds prev, so each node knows both neighbours.

Here n is the number of nodes. Prompts usually mean singly linked unless they say otherwise, but ask. A circular list is a third shape: the tail points back at the head, no next is ever None, and a walk stops when it gets back to the node it started from.

Most prompts don't hand you a node class, and an interviewer notices when writing one eats five minutes. Learn this by heart, along with two helpers that turn a Python list into a linked list and back. They make every test you run one line long.

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

def build(values):
    dummy = Node(None)
    tail = dummy
    for v in values:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head is not None:
        out.append(head.val)
        head = head.next
    return out

build puts a throwaway node in front of the real head so that every append looks the same. The next section turns that trick into a habit. If you prefer @dataclass, write @dataclass(eq=False). The default makes nodes unhashable, so you can't put them in a set or use them as dictionary keys, and its generated == walks the next fields recursively, at least one stack frame per node.

A dummy head makes the first node ordinary

Most list edits follow one recipe: walk to the node just before the spot you're changing, then rewire its next. The head breaks the recipe because nothing sits before it. Without help, every insert and delete grows an if index == 0 branch, and that branch is where the bugs collect.

A dummy head (also called a sentinel) is a placeholder node you create in front of the real head. Now every real node, the first included, has a node before it, so one code path handles them all. At the end you return dummy.next, which is the real head after the edit, whether or not it changed.

def node_before(dummy, index):
    """Return the node just before position index; the dummy sits at -1."""
    prev = dummy
    for _ in range(index):
        if prev.next is None:
            raise IndexError(index)
        prev = prev.next
    return prev

def insert_at(head, index, val):
    dummy = Node(None, head)
    prev = node_before(dummy, index)
    prev.next = Node(val, prev.next)
    return dummy.next

def delete_at(head, index):
    dummy = Node(None, head)
    prev = node_before(dummy, index)
    if prev.next is None:
        raise IndexError(index)
    prev.next = prev.next.next
    return dummy.next

The shared helper puts the off-by-one question in one place: the walk begins on the dummy at position -1 and steps index times, so it stops on position index - 1. Both edits cost O(i) time, where i is the index, and O(1) extra space.

"I'll put a dummy node in front of the head so that deleting the first node goes through the same code as deleting any other. At the end I return dummy.next, because the head may have changed."

The common mistake shows up in the caller. If you call delete_at(head, 0) and keep using head, you are holding the node you just removed, and the interviewer sees your test print a list that still starts with the deleted value. A function that can change the head returns it, and the caller reassigns: head = delete_at(head, 0). The same slip inside the function is returning head instead of dummy.next.

The dummy also pays off when you build a new list: keep a tail pointer, attach each new node after it, and return dummy.next, as build does.

Draw the pointers, then reverse with three

Before you write a pointer assignment, draw the nodes as boxes with arrows and write each variable's name over the box it refers to. For each assignment you plan, cross out the arrow it replaces and check whether any box is now unreachable. A node with no arrow into it, from a variable or from another node, is gone for good. If a step would orphan a node, save a reference to it first.

Reversing a list in place shows why. Three pointers do the work: prev is the head of the part already reversed, curr is the node being flipped, and nxt holds on to everything after curr. Here is the drawing for 1 → 2 → 3, one row per pass of the loop:

Each pass flips one arrow. When curr runs off the end, prev is the old tail, which is the new head.

def reverse(head):
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next   # hold on to the rest of the list
        curr.next = prev  # flip this node's arrow
        prev = curr       # step both pointers forward
        curr = nxt
    return prev           # the old tail is the new head

That is O(n) time and O(1) extra space. The order of the four lines in the loop is the whole algorithm, so say it while you write it:

"prev is the reversed part and curr is the node I'm flipping. I save curr.next in nxt first, because the next line overwrites it. When curr is None, prev is the new head."

The mistake interviewers see most is flipping curr.next before saving it. The following line then follows the new arrow backward, the loop ends after one pass, and the function returns a one-node list. Tracing three nodes on the board catches it in under a minute. Then trace the edges: an empty list returns None without entering the loop, and a single node comes back as itself.

A fast and a slow pointer find the middle

To find the middle without counting first, start two pointers at the head. slow moves one node per step and fast moves two, so when fast reaches the end, slow has covered half the distance. That is one pass instead of two (count, then walk to n/2), although both are O(n) time and O(1) extra space. The second function cuts the list into a front list and a back list, the first step whenever you need to work on each part separately, such as a merge sort on a linked list.

def middle(head):
    """The middle of the list; for an even count, the second of two."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

def split_front_back(head):
    """Cut the list in two; the front keeps the extra node of an odd count."""
    if head is None:
        return None, None
    slow, fast = head, head.next
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    back = slow.next
    slow.next = None
    return head, back

Which middle you get depends on where fast starts. With both pointers on the head, an even count gives the second of the two middles (node 3 of 4). Starting fast one node ahead gives the first (node 2 of 4), which is what split_front_back needs: it must stop on the last node of the front part to cut its next. Decide which one you want, say so, and test lengths 1 through 4.

The loop condition is the other trap. In middle, while fast.next is not None on its own crashes on an empty list and on every even length (in split_front_back, on every odd length), because fast itself becomes None and None.next raises AttributeError. Check fast first, then fast.next.

Recursion costs a stack frame per node

A list is defined recursively (a node followed by a shorter list), so recursive code fits it: def length(node): return 0 if node is None else 1 + length(node.next). That looks free of memory use, but each call waits on the one after it, so a list of n nodes holds n frames on the call stack at once, which is O(n) space. The 1 + runs after the inner call returns, so this isn't a tail call, and Python wouldn't eliminate one anyway. CPython's default recursion limit is 1,000 frames, so that one-liner raises RecursionError on a 5,000-node list. Raising the limit with sys.setrecursionlimit only moves the wall, and an interviewer's follow-up is often a much longer list.

So state the stack cost whenever you write recursive list code, and offer the loop when the list could be long:

"This recursive version is O(n) time and O(n) stack. If the list can be long, I'd use the loop, which needs O(1) extra space."

Recursion is most tempting when the work happens on the way back, such as visiting values from last to first. There you can push the nodes onto your own stack and pop them, which the next lesson, When a stack or queue is the answer, shows in general.

Practicing with these questions

Work each question in a plain editor or on paper before you run anything. Draw three or four nodes, write which pointers each step changes, then code. Trace the empty list, one node and two nodes by hand, because that is where interviewers look first. Time yourself writing Node, build and to_list: if they take under two minutes, the rest of the round goes to the problem.

Use Remove Target Values from a Linked List as a warm-up: before you call it done, trace a list whose first two nodes both match and a list where every node matches. The copy question below is the hardest here. Its nodes carry a second kind of pointer, so draw both kinds of arrow before you decide what to store. For shorter problems on the same moves, work through the Blind 75 linked list set.