Linked List Techniques (Dummy Node, In-Place Reversal)

Linked lists are where clean algorithmic thinking goes to get tangled in null checks. The logic of "reverse this stretch" or "delete this node" is trivial; the bugs all live at the edges, when the node you are touching is the head, or the tail, or the list is empty. Two small techniques defuse almost all of that pain: a dummy (sentinel) node that removes the head as a special case, and in-place reversal that rewires pointers without allocating anything. Neither is deep. Both are the difference between code that works and code that works except on the first element.

In-place reversal: the pointer dance

Reversing a singly linked list looks like it should need a second list, but it does not. You walk the list once, flipping each next pointer to face backward, carrying three references so you never lose your place.

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

def reverse(head):
    prev = None
    while head:
        nxt = head.next        # remember where we were headed
        head.next = prev       # flip this link to face backward
        prev = head            # slide both cursors forward
        head = nxt
    return prev                # prev is the new head

The nxt stash is the whole trick: the instant you overwrite head.next, the rest of the list would be lost, so you grab it first. O(n) time, O(1) space, and the same three-pointer dance reverses a sublist too, once you have pointers to its edges.

A list 1-2-3-4 shown before and after in-place reversal; walking once and flipping each next pointer to face backward turns it into 4-3-2-1, moving the head from node 1 to node 4 using only constant extra space by stashing the next node before overwriting each link.

In the wild: the sentinel nodes of an LRU cache

The dummy-node idea earns its keep in one of the most common structures in real systems: the least-recently-used cache. An LRU keeps entries in a doubly linked list ordered by recency, moving an entry to the front whenever it is used and evicting from the back when full. Both operations are O(1), but only if you never have to ask "is this the head or the tail." The trick is to start the list with two permanent sentinel nodes, a head and a tail that hold no data and never move.

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

class RecencyList:
    def __init__(self):
        self.head, self.tail = Node(), Node()   # sentinels, always present
        self.head.next, self.tail.prev = self.tail, self.head

    def add_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = self.head.next = node

    def remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

Look at what is missing: there is not a single if node is None or "is this the head" branch. Because the sentinels are always there, every real node is guaranteed to have a real prev and next, so add_front and remove are just four pointer assignments with no edge cases. That is the same lesson as the reversal, one level up: a tiny bit of structure, a stashed pointer or a pair of dummy nodes, buys you code with no special cases and no extra memory. It is why production caches, and plenty of kernel data structures, are built on sentinels.

The trigger

A singly or doubly linked list problem where the messy part is manipulating nodes at the boundaries, deleting the head, reversing a segment, splicing near the ends. If you find yourself writing a special case for "when it is the first node," reach for a dummy node. If you need to reverse without extra space, reach for the three-pointer walk.

Where it shows up

  • Reversal: whole list, a sublist between two positions, or in fixed-size groups.
  • Deletion and insertion at the head: remove the Nth node from the end, dedup a sorted list, all cleaner with a dummy before the head.
  • Ordered structures with O(1) splicing: LRU caches and other recency or priority lists built on doubly linked nodes.

Where it bites

The bugs are the ones you would expect from manual pointer surgery: overwrite a next before stashing it and you orphan the rest of the list; forget to update a prev in a doubly linked list and it silently corrupts in one direction only, which is miserable to debug. Reversal boundaries are their own hazard, connecting the reversed segment back to the nodes on either side is where off-by-one lives.

When it is the wrong tool

Reach for a different structure entirely if you need random access, because a linked list makes "the k-th element" an O(n) walk where an array is O(1). If you are reversing only in order to read the list backward once, storing the values in an array or a stack is simpler than rewiring pointers. In most application code you should lean on library containers rather than hand-rolling nodes at all; these techniques matter most in interviews and in low-level systems, allocators, kernels, intrusive lists, where an O(1) splice or zero allocation genuinely pays.

Its neighbors

It leans directly on Fast & Slow Pointers, which locate the middle or a cycle before you rewire anything, and shares its pointer-juggling mindset with Two Pointers. The recency-list example is the beating heart of the LRU cache you will meet again in Design Problems.

References