Linked Lists

Dummy heads, reversal, fast/slow pointers and merging without losing nodes.

Linked list problems rarely need clever algorithms. They test whether you can rewire pointers without losing nodes. A handful of techniques covers almost every question: a dummy head, reversal, fast and slow pointers, and merging.

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

1. The dummy head

Whenever the head itself might change (removing the first node, merging, partitioning), start with a sentinel node in front of it. You never need to special-case an empty result, and you return dummy.next at the end.

def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next     # unlink, don't advance
        else:
            prev = prev.next
    return dummy.next

2. Reversal

Reversal is worth memorizing exactly. It's a building block for palindrome checks, reordering, and reversing in groups of k.

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next      # save before overwriting
        curr.next = prev
        prev, curr = curr, nxt
    return prev

[!TIP] Draw it Sketch three boxes and arrows, and update them as you narrate each line. Pointer bugs are much easier to spot on paper than in your head, and interviewers like seeing the check.

3. Fast and slow pointers

Move one pointer two steps at a time and the other one step:

Middle of the list: when fast reaches the end, slow is in the middle.
Cycle detection: if they ever meet, there's a cycle (Floyd's algorithm).
Start of the cycle: after they meet, reset one pointer to the head and move both one step at a time. They meet again at the cycle's entrance.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

4. Two pointers with a gap

To remove the nth node from the end in one pass, advance fast n steps, then move both pointers until fast reaches the last node. slow then sits just before the node to delete. Use a dummy head so that removing the first node works too.

5. Merging

def merge(a, b):
    dummy = tail = ListNode()
    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
    return dummy.next

Merging k lists means a heap of the current heads, O(n log k). Sorting a list means merge sort: split at the middle with fast and slow pointers, sort each half, then merge.

Combining the techniques

Harder problems chain the basics together. Reorder list (L0 → Ln → L1 → Ln−1 …) has three steps:

Find the middle (fast/slow).
Reverse the second half.
Merge the two halves, alternating nodes.

Palindrome list uses the same first two steps, then compares the halves. If the interviewer cares about leaving the input unchanged, restore the list afterwards.

Edge cases to test

An empty list, or a single node
Two nodes. This is where off-by-one errors in fast/slow pointers show up.
Operations that touch the head or the tail
Lists with even vs odd lengths

[!WARNING] Don't lose the rest of the list Before you overwrite node.next, make sure something else still points at the old next node. Most linked list bugs are an overwrite that happens one line too early.

[!TIP] Practice Reverse Linked List · Merge Two Sorted Lists · Linked List Cycle II · Remove Nth from End · Reorder List · Add Two Numbers · Reverse Nodes in k-Group · Merge k Sorted Lists