L19 · Linked Lists I — Traversal & Reversal

Series: LeetCode — From Basics to Interview-Ready · Session 19 / 65 · Phase 1 · Core patterns

Why this session exists

The dummy head eliminates most linked-list edge cases. Use it by default and stop thinking about it.

Linked-list problems are rarely algorithmically hard. Nobody is asking you to invent anything — reversing a list, merging two sorted lists, deleting a node — these are operations a first-year student understands conceptually. What they test is whether you can execute pointer surgery without dropping anything, and specifically whether you can do it at the boundaries: empty list, single node, operation affecting the head itself.

Almost every bug in this category is a boundary bug. The middle of the list is easy; the ends are where people lose nodes. The dummy head is a two-line trick that makes the head stop being special, and it converts a category of problems from fiddly to mechanical.

The second half of the session is the reversal loop. It is four lines, you will use it in Reorder List, in Palindrome Linked List, in Reverse Nodes in k-Group, and in a dozen others. It must be muscle memory. If you have to derive it during an interview you have spent budget you needed elsewhere.

Blank-file warm-up

Five minutes, empty file, no notes. Write the reversal loop:

prev = None
while cur:
    nxt = cur.next
    cur.next = prev
    ...

Complete it, then write what the function returns and why it is not cur.

Then, separately, write a merge of two sorted lists using a dummy head, from scratch. If you find yourself writing if not head: return other special cases at the top, you have not internalised the dummy — that is today's finding.

Pattern anatomy

The shape that summons this pattern: you must relink nodes, and the operation can affect the first node.

Two tools, and the invariants that make them work.

The reversal loop. Invariant: at the top of every iteration, everything from the original head up to but excluding cur has been reversed, and prev points at the head of that reversed portion.

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next        # 1. SAVE the rest before you destroy the link
        cur.next = prev       # 2. FLIP this node's pointer backward
        prev = cur            # 3. ADVANCE prev to the node just processed
        cur = nxt             # 4. ADVANCE cur to the saved next
    return prev               # cur is None here; prev is the new head

Four lines in a fixed order, and the order is not negotiable. Line 1 must come before line 2, because line 2 overwrites the only reference to the rest of the list. Lines 3 and 4 must come after both, and in that order, because line 4 depends on nxt and line 3 must capture cur before it moves.

Return prev, not cur. When the loop exits, cur is None — it walked off the end. prev is the last node processed, which was the original tail, which is the new head. Returning cur returns an empty list, and it is the single most common slip on this function.

The dummy head. Invariant: dummy.next is always the true head of the result, and tail always points at the last node committed to the result.

def merge_two_lists(a, b):
    dummy = ListNode()          # sentinel; its value is never read
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b          # attach whichever still has nodes
    return dummy.next           # skip the sentinel

No emptiness checks anywhere. If both inputs are empty, the loop never runs, tail.next = None, and dummy.next is None — correct. If one is empty, the loop never runs and the other is attached wholesale — correct. The sentinel absorbs every boundary case because it guarantees there is always a node to attach to, even before the first real node exists.

tail.next = a or b uses Python truthiness: a non-empty node object is truthy, None is falsy. It attaches the remaining list, or None when both are exhausted. If that is too clever for your taste, write the explicit if, but understand why the one-liner is correct.

Two-pointer with a gap. For "nth from the end", advance a lead pointer n steps first, then move both until the lead falls off. The trailing pointer lands n from the end, in one pass:

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)          # dummy so removing the head is not special
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:                   # stop with fast ON the last node
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next         # slow is the node BEFORE the target
    return dummy.next

The dummy is doing real work here. To delete node k you need a handle on node k − 1, and when k is the head there is no such node — unless a dummy provides one. Without it, removing the first element needs an entirely separate code path.

The cue

How you recognise this from the problem statement:

1. Any operation that can remove or replace the first node. Delete, insert-at-front, partition, remove-duplicates-including-the-first. Reach for the dummy before writing anything else.
2. "Reverse" in any form — whole list, sublist, in groups of k, alternating. The four-line loop is the atom in all of them.
3. "Nth from the end", "middle", "kth from last". Two pointers with a fixed gap, or slow and fast at different speeds. One pass, no length precomputation.
4. Merge, interleave, or zip two lists. Dummy head plus a tail pointer. This is also the merge step of merge sort on lists.
5. A stated constraint of O(1) extra space. That rules out copying to an array, which is otherwise the pragmatic answer to half these problems. When you see it, the problem wants pointer manipulation specifically.

The anti-cue: if you need random access by index, or you need to walk backward, a singly linked list is the wrong tool and the problem probably intends for you to say so. Converting to an array is a legitimate answer when no space constraint is stated — say what it costs and let the interviewer object if they want the pointer version.

Guided solve

Reverse Linked List. Given the head of a singly linked list, reverse it and return the new head.

The difficulty here is entirely about not losing the list. A singly linked list gives you exactly one reference to each node's successor, so the moment you overwrite cur.next, the remainder of the list is unreachable unless you saved it first. Every correct solution is organised around that single fact.

Take 1 -> 2 -> 3 -> None.

Initial: prev = None, cur = 1.

Iteration 1: nxt = 2 (saved). 1.next = None — the list is now 1 -> None and separately 2 -> 3 -> None, held only by nxt. prev = 1, cur = 2.

Iteration 2: nxt = 3. 2.next = 1, so the reversed portion is 2 -> 1 -> None. prev = 2, cur = 3.

Iteration 3: nxt = None. 3.next = 2, giving 3 -> 2 -> 1 -> None. prev = 3, cur = None.

Loop exits. Return prev = 3. Head of 3 -> 2 -> 1 -> None. Correct.

Now check the boundaries without changing any code. Empty list: cur = None, loop body never executes, return prev = None. Correct. Single node: one iteration, nxt = None, 1.next = None, return prev = 1. Correct. No special cases needed — which is worth pointing out explicitly in an interview, because it demonstrates you checked rather than hoped.

The recursive form exists and is worth being able to write, though I would not lead with it:

def reverse_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head      # the node after head now points BACK to head
    head.next = None           # head becomes the tail
    return new_head            # unchanged all the way up the stack

head.next.next = head is the whole thing, and it is genuinely hard to read. It says: my successor, which is now the tail of the already-reversed remainder, should point back at me. The recursion also costs O(n) stack, which fails the O(1) space constraint these problems usually state. Know it, but write the iterative version.

Solo timed

15 minutes each, timer visible.

• Merge Two Sorted Lists — dummy head plus a tail pointer; after the main loop, tail.next = a or b to attach whatever remains. Do not write emptiness checks at the top; verify afterward that the dummy handled them.
• Remove Nth Node From End of List — dummy, then advance fast exactly n steps, then move both until fast.next is None. Test with n equal to the list length, which is the case where the head itself is removed and where the dummy earns its place.

If you finish early: reverse the list, then reverse it again, and assert you got the original back. Any lost node shows up immediately.

Common failure modes

Overwriting cur.next before saving it. The rest of the list becomes unreachable. Save first, always. This is the one bug that loses data rather than producing a wrong answer.

Returning cur instead of prev from the reversal. Returns None. Total failure from one character.

Not using a dummy when the head can change. Forces a separate branch for head removal, and that branch is usually the untested one. Two lines of dummy replace ten lines of special case.

Losing the tail pointer's synchronisation. In merge, forgetting tail = tail.next after attaching means every subsequent attachment overwrites the previous one, and the result is a two-node list. Silent and confusing.

Off-by-one in the gap advance. For nth-from-end, advancing fast by n from the dummy and looping while fast.next leaves slow on the node before the target. Advancing by n + 1 or looping while fast instead of fast.next shifts you one node and deletes the wrong element.

Creating a cycle. In problems where you reverse a portion and reattach, forgetting to set the old head's next to None leaves a link back into the reversed section. The symptom is an infinite loop on traversal, which in a submission looks like a timeout rather than a wrong answer.

Complexity

Reverse Linked List — Time: O(n), Space: O(1). Each node is visited exactly once and its next pointer written exactly once. The only storage is three pointer variables, independent of list length. The recursive version is O(n) time but O(n) space from the call stack.

Merge Two Sorted Lists — Time: O(m + n), Space: O(1). Every node from both inputs is examined once and relinked once. No new nodes are allocated except the single sentinel, which is O(1) and discarded on return. Note this is genuinely O(1) auxiliary — the returned list reuses the input nodes rather than copying them, which is why the function mutates its arguments.

Remove Nth From End — Time: O(n), Space: O(1). The fast pointer traverses the whole list once; slow traverses at most all of it. Two passes' worth of work in one pass, which is the point of the gap technique — the naive version computes the length first and then walks again, and while that is also O(n), stating "one pass" is what the follow-up question asks for.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Reverse Linked List enters today and should be re-tested more often than its difficulty suggests. It is a dependency of at least four later problems, and being slow on it is expensive out of proportion to its own value.