The earlier linked-list pages are pure pointer work: fast and slow for structure, reversal for direction, dummy heads for building. This page covers the problems that need something more:

• A hash map, when a node’s copy must be found before it has been created.
• A composed traversal, when the answer is three known techniques applied in sequence.
• Careful field maintenance, when nodes carry more than nextnext.

These are the linked-list problems most likely to appear in a senior loop, because they test whether you can keep several invariants straight at once rather than execute one memorised template.

What you’ll learn

• The map-then-wire two-pass deep copy, and the $O(1)$-space interleaving alternative.
• Why reorder list is three patterns composed, and the order they must run in.
• Multilevel flattening, and the two fields you must not forget.
• The habit that prevents most bugs here: name what each pointer means before touching it.
• Three real LeetCode problems solved in the browser: 138, 143, 430.

The cue

Pattern 1 — map then wire

For LC 138 each node has a randomrandom pointer that may target any node, including one you have not copied yet. So you cannot wire pointers while creating nodes — the target may not exist.

Two passes solve it:

def copy_random_list(head):
    if not head:
        return None
 
    clone = {}                          # original node -> its copy
 
    node = head                         # PASS 1: create every copy
    while node:
        clone[node] = Node(node.val)
        node = node.next
 
    node = head                         # PASS 2: wire, now that all exist
    while node:
        clone[node].next = clone.get(node.next)       # .get -> None for None
        clone[node].random = clone.get(node.random)
        node = node.next
 
    return clone[head]

def copy_random_list(head):
    if not head:
        return None
 
    clone = {}                          # original node -> its copy
 
    node = head                         # PASS 1: create every copy
    while node:
        clone[node] = Node(node.val)
        node = node.next
 
    node = head                         # PASS 2: wire, now that all exist
    while node:
        clone[node].next = clone.get(node.next)       # .get -> None for None
        clone[node].random = clone.get(node.random)
        node = node.next
 
    return clone[head]

$O(n)$ time, $O(n)$ space for the map.

Pattern 2 — composition

LC 143 asks you to reorder 1→2→3→4→51→2→3→4→5 into 1→5→2→4→31→5→2→4→3. That is not a single technique; it is three, in a fixed order:

def reorder_list(head):
    if not head or not head.next:
        return head
 
    # 1. find the middle (fast/slow) and SPLIT
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    second = slow.next
    slow.next = None                      # ESSENTIAL: terminate the first half
 
    # 2. reverse the second half
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
 
    # 3. interleave the two halves
    first, second = head, prev
    while second:
        first_next, second_next = first.next, second.next   # name them first
        first.next = second
        second.next = first_next
        first, second = first_next, second_next
 
    return head

def reorder_list(head):
    if not head or not head.next:
        return head
 
    # 1. find the middle (fast/slow) and SPLIT
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
    second = slow.next
    slow.next = None                      # ESSENTIAL: terminate the first half
 
    # 2. reverse the second half
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
 
    # 3. interleave the two halves
    first, second = head, prev
    while second:
        first_next, second_next = first.next, second.next   # name them first
        first.next = second
        second.next = first_next
        first, second = first_next, second_next
 
    return head

The loop condition while fast.next and fast.next.nextwhile fast.next and fast.next.next makes slowslow land on the end of the first half for both odd and even lengths — which is what you want, since the first half may be one longer. Using while fast and fast.nextwhile fast and fast.next instead lands slowslow one further along and breaks the even case.

Pattern 3 — maintain every field

LC 430 flattens a doubly linked list where nodes may have a childchild list. The algorithm is simple; the bookkeeping is where it goes wrong.

def flatten(head):
    if not head:
        return None
 
    node = head
    while node:
        if node.child:
            nxt = node.child              # splice the child list in here
            tail = nxt
            while tail.next:              # walk to the child list's end
                tail = tail.next
 
            after = node.next             # remember what came after
            node.child = None             # MUST be cleared
            node.next = nxt
            nxt.prev = node
 
            tail.next = after
            if after:
                after.prev = tail         # only if there IS a node after
        node = node.next
 
    return head

def flatten(head):
    if not head:
        return None
 
    node = head
    while node:
        if node.child:
            nxt = node.child              # splice the child list in here
            tail = nxt
            while tail.next:              # walk to the child list's end
                tail = tail.next
 
            after = node.next             # remember what came after
            node.child = None             # MUST be cleared
            node.next = nxt
            nxt.prev = node
 
            tail.next = after
            if after:
                after.prev = tail         # only if there IS a node after
        node = node.next
 
    return head

Three things must all be right: nextnext, prevprev, and child = Nonechild = None. The problem explicitly requires all childchild pointers to be null in the result, and it is the one most easily forgotten because the list looks correct when you walk it forwards.

The variant map

Practice — real LeetCode problems

LC 138 — Copy List with Random Pointer · Medium

Problem. Each node has a valval, a nextnext and a randomrandom pointer that may point to any node in the list or to NoneNone. Return a deep copy: entirely new nodes, with nextnext and randomrandom pointing to the corresponding copies.

Constraints. 0 <= n <= 10000 <= n <= 1000, -10^4 <= Node.val <= 10^4-10^4 <= Node.val <= 10^4.

Examples. For [[7,null],[13,0],[11,4],[10,2],[1,0]][[7,null],[13,0],[11,4],[10,2],[1,0]] the copy must have the same values and the same randomrandom structure — and share no nodes with the original.

LC 143 — Reorder List · Medium

Problem. Given L0 → L1 → … → Ln-1 → LnL0 → L1 → … → Ln-1 → Ln, reorder it to L0 → Ln → L1 → Ln-1 → L2 → …L0 → Ln → L1 → Ln-1 → L2 → …. You may not modify the values, only rearrange nodes.

Constraints. 1 <= n <= 5 * 10^41 <= n <= 5 * 10^4, 1 <= Node.val <= 10001 <= Node.val <= 1000.

Examples. [1,2,3,4][1,2,3,4] gives [1,4,2,3][1,4,2,3] · [1,2,3,4,5][1,2,3,4,5] gives [1,5,2,4,3][1,5,2,4,3]

LC 430 — Flatten a Multilevel Doubly Linked List · Medium

Problem. A doubly linked list where nodes may additionally have a childchild pointer to another such list. Flatten it into a single-level doubly linked list, with child lists appearing immediately after their parent node. All childchild pointers in the result must be NoneNone.

Constraints. 0 <= number of nodes <= 10000 <= number of nodes <= 1000.

Examples. 1-2-3-4-5-61-2-3-4-5-6 with 3.child = 7-8-9-103.child = 7-8-9-10 and 8.child = 11-128.child = 11-12 flattens to 1-2-3-7-8-11-12-9-10-4-5-61-2-3-7-8-11-12-9-10-4-5-6

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Empty list — NoneNone in, NoneNone out for all three.
• Single node — 143 returns it unchanged; 138 must still deep-copy it.
• Two nodes — 143’s smallest interleave; also where the wrong fast/slow condition first shows up.
• randomrandom pointing to NoneNone — must map to NoneNone, not raise.
• randomrandom pointing to itself or backwards — both legal; the map handles them.
• All randomrandom pointers NoneNone — reduces to a plain copy.
• Child at the last node (LC 430) — afterafter is NoneNone, so guard after.prevafter.prev.
• Nested children — 8’s child inside 3’s child; the inline walk covers it.
• Odd vs even length (LC 143) — [1,2,3][1,2,3] gives [1,3,2][1,3,2]; the first half may be longer.
• Forgetting to terminate a split — produces a cycle and a timeout, not a wrong answer.

Recap

• When a pointer can target a node that does not exist yet, create everything first and wire second — a dictdict from original to copy. Use .get().get() so NoneNone maps to NoneNone.
• The $O(1)$-space deep copy interleaves copies into the original list, making the list itself the map: orig.random.nextorig.random.next is the copy of orig.randomorig.random.
• Reorder List is a composition: find the middle, split, reverse the second half, interleave. The slow.next = Noneslow.next = None split is what prevents a cycle.
• Name pointers in locals before rewiring. Every bug in this family is a lost reference.
• When nodes carry extra fields, maintain all of them — nextnext, prevprev, and clearing childchild.
• Splicing a nested list inline and continuing the walk handles arbitrary nesting with no recursion.
• LC 138 and LC 133 are the same problem; the map doubles as the visited set on a graph.

Next: the tree patterns — recursion over branching structures rather than linear ones.