Copy Flatten and Reorder

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 next.

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

You are looking at this family when…

• Nodes have extra pointers beyond next — random, child, prev — 138, 430, 426.
• You must deep copy a structure whose references point anywhere — 138, 133 (the graph version).
• The target arrangement interleaves parts of the list — 143, 328.
• A nested list must be linearised — 430.
• The solution is clearly “find the middle, then reverse, then merge” — that composition is the tell for 143 and 234.

Visual intuition

Reorder List (LC 143) is three known techniques composed, and two of them have traces already. Half two gets reversed in place:

listStep 2 of Reorder List: reverse the second half in placeprev / curr / next

1def reverse(head):2    prev, cur = None, head3    while cur:4        nxt = cur.next        # 1. SAVE the rest of the list5        cur.next = prev       # 2. flip this node's arrow6        prev = cur            # 3. advance prev7        cur = nxt             # 4. advance cur8    return prev               # prev is the new head

prevNonecur4

setupThree pointers, and the order of the four assignments inside the loop is everything. prev starts at null because the old head becomes the new tail — its next must end up pointing at nothing.

Play‹›1/8⟲

This is the whole of In-place Linked List Reversal applied to a sublist. The first half is untouched -- which only works because slow.next was set to None first, terminating it. Forget that line and this reversal walks back into the first half and builds a cycle.

Then the two halves are interleaved, which is the merge shape with an alternating rule instead of a comparison:

listStep 3: splice the reversed half into the first, one node eachthe same two-cursor rewiring

remaininga:1a:2a:3b:5b:4

1def merge(a, b):2    dummy = tail = ListNode(0)   # dummy avoids an empty-list special case3    while a and b:4        if a.val <= b.val:       # <= keeps the merge STABLE5            tail.next = a; a = a.next6        else:7            tail.next = b; b = b.next8        tail = tail.next9    tail.next = a or b           # attach whatever is left, in one line10    return dummy.next

a1,2,3b5,4

setupThe dummy node is the whole technique. Without it, the first append needs a special case ("is the result empty yet?"), and that branch is where linked-list code goes wrong. With it, "tail.next = x" is unconditionally correct, and the real head is just "dummy.next" at the end.

Play‹›1/6⟲

A sorted merge picks by comparison; the interleave picks by strict alternation. The pointer surgery is identical, which is the point of this page -- these problems are compositions of techniques you already have, not new algorithms.

Pattern 1 — map then wire

For LC 138 each node has a random 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:

copy_random_list.py

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.

clone.get(...) rather than clone[...]

node.next is None at the tail, and node.random may be None anywhere. clone[None] raises KeyError; clone.get(None) returns None — which is exactly the value the copy’s pointer should have.

You could instead seed the map with clone[None] = None and index directly. Both are fine; the point is to handle None deliberately rather than discover it via a crash.

The $O(1)$-space version, if asked

There is a well-known constant-space alternative: interleave the copies into the original list, so each copy sits immediately after its original.

1. Weave: A -> A' -> B -> B' -> C -> C'.
2. Set each copy’s random: A'.random = A.random.next — because A.random.next is the copy of A.random. That is the trick: the original list itself becomes the map.
3. Unweave into two separate lists, restoring the original.

$O(n)$ time, $O(1)$ extra space. It is the expected answer when an interviewer says “now without the hash map”, and step 2 is the insight worth remembering.

Pattern 2 — composition

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

reorder_list.py

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

slow.next = None is not optional

Without it the first half still points into the second, and after reversing you get a cycle — the interleave loop never terminates and the judge times out rather than reporting a wrong answer.

Any time you split a list, terminate the piece you keep. The same warning applies to Partition List.

The loop condition while fast.next and fast.next.next makes slow 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.next instead lands slow 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 child list. The algorithm is simple; the bookkeeping is where it goes wrong.

flatten_multilevel.py

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: next, prev, and child = None. The problem explicitly requires all child 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.

Problem	Time	Space
138 with a map	$O(n)$	$O(n)$
138 interleaved	$O(n)$	$O(1)$
143 reorder	$O(n)$	$O(1)$
430 flatten	$O(n)$	$O(1)$ iterative, $O(\text{depth})$ recursive

Dry run

Reorder List — 1 → 2 → 3 → 4 → 5. Three phases, each one a technique from an earlier page:

phase	state afterwards
1. Split at the middle (fast/slow), then slow.next = None	1→2→3 and 4→5
2. Reverse the second half	1→2→3 and 5→4
3. Interleave, one node from each	1→5→2→4→3

Answer 1 → 5 → 2 → 4 → 3. On the even-length input 1→2→3→4 the same code gives 1→4→2→3.

• slow.next = None is the load-bearing line. Without it, the first half still points into the second, and the reversal in phase 2 walks back through nodes the first half also references — producing a cycle rather than two lists. The symptom is an infinite loop in the interleave, far from the cause.
• The split lands where fast runs out, so for odd lengths the first half gets the extra node (1→2→3 versus 4→5). That asymmetry is what makes the interleave terminate cleanly: the loop condition is while second, and the first half is never shorter.
• Phase 3 names both successors before rewiring — first_next, second_next = first.next, second.next. Rewire before naming and you lose the rest of one list; this is the same assignment-order discipline as the dummy-head page.
• Nothing is allocated. All three phases move pointers, so the whole thing is $O(1)$ extra space — which is exactly what the problem’s follow-up asks for and why the copy-into-an-array solution, while correct, misses the point.

Copy with random pointers (LC 138) — why two passes. Pass 1 creates every clone and records original → clone in a dict; pass 2 wires clone[node].next and clone[node].random. A single pass cannot work: node.random may point forward to a node whose clone does not exist yet. clone.get(node.next) rather than clone[node.next] is what makes the tail’s None safe.

Complexity

Problem	Time	Space
LC 138 Copy List with Random Pointer, hash map	$O(n)$	$O(n)$ for the map
LC 138, interleaved-nodes trick	$O(n)$	$O(1)$ — weave clones into the original list, then unweave
LC 143 Reorder List	$O(n)$	$O(1)$
LC 143 via an array of nodes	$O(n)$	$O(n)$
LC 430 Flatten a Multilevel List, iterative splice	$O(n)$	$O(1)$
LC 430 with an explicit stack	$O(n)$	$O(d)$, d = nesting depth

The pattern across all three: the $O(n)$-space solution is the obvious one, and the interview is about the $O(1)$ version. For LC 138 that means the weave trick — put each clone directly after its original, so original.next is the clone and the random wiring becomes clone.random = node.random.next with no dictionary at all, then unweave. Say the hash-map solution first; it is correct and clear, and then improve it.

The variant map

Variant	The technique	Canonical problem
Deep copy with arbitrary pointers	Map then wire, or interleave	138
Deep copy a graph	The same map, with DFS/BFS	133
Interleave halves	Middle + reverse + merge	143
Flatten a nested list	Splice each child list inline	430
BST to doubly linked list	In-order traversal, relinking as you go	426 (Premium)
Split by odd/even position	Two dummy heads	328
Palindrome check	Middle + reverse + compare	234

Practice — real LeetCode problems

LC 138 — Copy List with Random Pointer · Medium

Problem. Each node has a val, a next and a random pointer that may point to any node in the list or to None. Return a deep copy: entirely new nodes, with next and random pointing to the corresponding copies.

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

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

What this test checks

It verifies three things: the copied values in order, the value each copy’s random points at, and — crucially — that no copied node is the same object as its original. A shallow copy would pass the first two checks and fail the third.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The random pointer is the whole difficulty: it can point forwards, so at the moment you copy a node its random target may not exist yet. Separating creation from wiring removes the ordering problem entirely.

Time $O(n)$ — two passes. Space $O(n)$ for the map.

clone.get(...) handles None targets. Indexing with clone[None] raises, and adding an if node.random else None conditional on each line is noisier for the same effect.

Follow-ups you should expect:

• “Do it in $O(1)$ extra space.” The interleaving trick described above: weave copies in after their originals so that original.random.next is the copy of original.random, then unweave. This is the standard follow-up, and the key line is copy.random = original.random.next.
• “One pass instead of two?” Yes, with a defaultdict that creates a copy on first access — so a forward random reference creates the node early and the later next pass finds it already present. Neat, and worth knowing.
• “Deep copy a graph (LC 133)?” The same map, but traversal is DFS or BFS since there is no linear order.
• “Why not copy.deepcopy?” It works and is $O(n)$, but it defeats the question; mention it and move on.

LC 143 — Reorder List · Medium

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

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

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-uups

The target order takes one node from the front, then one from the back, alternating. Reversing the second half turns “from the back” into “from the front”, after which it is a straightforward interleave.

Time $O(n)$ — three linear passes. Space $O(1)$.

Three details, each with a reason:

• slow.next = None. Without it the first half still links into the second, and after reversal you have a cycle — the interleave loop spins forever and the submission times out rather than failing cleanly.
• while fast.next and fast.next.next. This lands slow on the last node of the first half for both parities. For [1,2,3,4] it stops with slow at 2, splitting [1,2] and [3,4]. Using while fast and fast.next puts slow one step further and breaks the even case.
• Name the pointers before rewiring. first_next and second_next must be captured before either next is overwritten, or you lose the rest of a list.

The odd case is worth tracing: [1,2,3,4,5] splits into [1,2,3] and [4,5], so the first half is longer. Reversing gives [5,4], and interleaving ends when second runs out, leaving 3 correctly at the tail.

The $O(n)$-space alternative — dump nodes into a list and re-link by index from both ends — is much easier to write and worth offering first if the pointer surgery is not flowing.

Follow-ups you should expect: “Palindrome check (LC 234)?” — the same middle plus reverse, then compare instead of interleave. “Restore the list afterwards?” — re-reverse the second half; mutating a caller’s input is a real design concern. “Odd Even Linked List (LC 328)?” — a different split (by position parity) with two dummy heads. “Why not use a deque?” — $O(n)$ space; fine, but the point is the $O(1)$ solution.

LC 430 — Flatten a Multilevel Doubly Linked List · Medium

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

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

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

What this test checks

Three things: the flattened order, that every child pointer is cleared, and that every node’s prev pointer is consistent with the node before it. It is easy to get the forward order right and leave the other two broken — and the problem requires all three.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Walk the list once. Whenever a node has a child, splice that child list in immediately after the node and clear the child pointer. Then keep walking from node.next — which is now the head of the spliced-in list, so any nested children inside it are handled by the same loop on a later iteration.

Time $O(n)$. Each node is visited once by the outer walk; the inner while tail.next walk visits each node at most once more in total across the whole run, because a child list is spliced exactly once. Space $O(1)$.

Three requirements must all hold, and the test checks each:

• Order — the child list comes immediately after its parent, before the parent’s original successor.
• child = None — explicitly required by the problem, and invisible if you only check the forward walk.
• prev pointers — both child.prev = node and after.prev = tail. The second needs an if after guard, since the parent may have been the last node.

The elegance is that no recursion or stack is needed. Because the walk continues into the spliced list, arbitrarily deep nesting resolves naturally — node 8’s child 11-12 is discovered on a later iteration of the same loop, after 7-8-9-10 has been spliced in.

A recursive or explicit-stack solution also works (push node.next, descend into node.child), and is $O(\text{depth})$ space. Worth mentioning; the iterative splice is neater.

Follow-ups you should expect: “Recursively?” — flatten the child, return its tail, splice; be careful returning tails correctly. “What if the child list also had children?” — already handled, and worth pointing out. “Flatten a nested iterator instead (LC 341)?” — lazy flattening; see Design Iterators. “Convert a BST to a sorted doubly linked list (LC 426)?” — in-order traversal relinking prev/next as you go.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 133 is LC 138 without the linear order

Clone Graph is the same deep-copy problem on a graph: nodes have arbitrary neighbours, so you cannot wire before creating.

The same original -> copy map works, but instead of two linear passes you do a single DFS or BFS, creating a copy on first visit and using the map to detect already-visited nodes. The map serves both as the copy registry and as the visited set — one structure, two jobs, which is why the traversal terminates on cycles.

If you can see 138 and 133 as the same problem, you have the pattern rather than the two solutions.

7 problems

0 easy7 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○133Clone GraphmediumThe same map-then-wire idea, with DFS/BFS instead of a linear walkNeetCode 150Blind 75LeetCode Top Interview 150metagoogleamazon
• ○138Copy List with Random PointermediumCreate all copies, then wire; or interleave for $O(1)$ spaceNeetCode 150LeetCode Top Interview 150amazonmicrosoftbloombergapple
• ○143Reorder ListmediumMiddle + reverse + interleave; the split is mandatoryNeetCode 150Blind 75amazonmetabloomberg
• ○148Sort ListmediumMerge sort -- see [Divide and Conquer](../../phase-11-recursion-and-backtracking/divide-and-conquer/)LeetCode Top Interview 150
• ○328Odd Even Linked ListmediumSplit by position parity with two dummy heads
• ○426Convert Binary Search Tree to Sorted Doubly Linked ListpremiummediumIn-order traversal, relinking as you visit
• ○430Flatten a Multilevel Doubly Linked ListmediumSplice inline; maintain `prev` and clear `child`

Interview follow-ups

They ask	What they’re checking	The answer
“Why two passes for the copy?”	The ordering problem	A random pointer may target a node not yet copied, so nothing can be wired until all nodes exist
“Do it in $O(1)$ space”	The known follow-up	Interleave copies after originals so orig.random.next is the copy of orig.random, then unweave
“Why does reorder need a split?”	Cycle awareness	Without slow.next = None the reversed half creates a cycle and the loop never ends
“Which fast/slow condition?”	Precision	while fast.next and fast.next.next lands slow at the end of the first half for both parities
“Did you clear child?”	Reading the spec	LC 430 requires it, and a forward walk looks correct without it
“Recursion or iteration for 430?”	Judgement	Iterative splicing is $O(1)$ space and handles nesting for free; recursion is $O(\text{depth})$
“Do you mutate the input?”	Design sense	143 and 430 do, by specification; say so, and offer to restore if it matters

Edge-case checklist

• Empty list — None in, None 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.
• random pointing to None — must map to None, not raise.
• random pointing to itself or backwards — both legal; the map handles them.
• All random pointers None — reduces to a plain copy.
• Child at the last node (LC 430) — after is None, so guard after.prev.
• Nested children — 8’s child inside 3’s child; the inline walk covers it.
• Odd vs even length (LC 143) — [1,2,3] gives [1,3,2]; the first half may be longer.
• Forgetting to terminate a split — produces a cycle and a timeout, not a wrong answer.

Self-check

pch.quizTag Copy, flatten and reorder — self-check

1. Why does copying a list with random pointers need two passes?

   A To handle cycles B Because `node.random` may point forward to a node whose clone does not exist yet — pass 1 creates every clone, pass 2 wires them C Because the list length is unknown D To avoid mutating the original
   pch.quizShowAnswer

   B — Because `node.random` may point forward to a node whose clone does not exist yet — pass 1 creates every clone, pass 2 wires them — Also note `clone.get(node.next)` rather than `clone[node.next]`: the tail's None is not a key, and .get returns None for it, which is exactly the value wanted.

2. In Reorder List, what breaks if you omit `slow.next = None` after finding the middle?

   A Nothing — the halves are already separate B The first half still points into the second, so reversing the second half creates a cycle — and the symptom is an infinite loop in the interleave, far from the cause C The list is reversed twice D The middle node is lost
   pch.quizShowAnswer

   B — The first half still points into the second, so reversing the second half creates a cycle — and the symptom is an infinite loop in the interleave, far from the cause — Splitting means terminating, not just locating. This single line is the difference between two lists and one list with a loop in it.

3. Reorder List is presented as three phases. What are they?

   A Sort, reverse, merge B Find the middle and split (fast/slow), reverse the second half in place, then interleave the two halves one node at a time C Copy to an array, reorder, rebuild D Reverse, split, merge
   pch.quizShowAnswer

   B — Find the middle and split (fast/slow), reverse the second half in place, then interleave the two halves one node at a time — Each phase is a technique from an earlier page. Recognising a hard problem as a composition of known ones — rather than a new algorithm — is what this page is teaching.

4. LC 138 can be solved in O(1) extra space. How?

   A Recursion instead of a dict B Weave each clone directly after its original so `original.next` IS the clone; then `clone.random = node.random.next` needs no map, and a final pass unweaves the two lists C Sort the nodes by address D It cannot; the map is required
   pch.quizShowAnswer

   B — Weave each clone directly after its original so `original.next` IS the clone; then `clone.random = node.random.next` needs no map, and a final pass unweaves the two lists — Lead with the hash-map solution — it is correct and clear — then offer this. The weave is the standard follow-up answer and it is hard to invent under pressure without having seen it.

5. Why does the interleave name both successors before rewiring?

   A For readability only B Because `first.next = second` destroys the pointer to the rest of the first list — you must save both successors before either assignment C To handle odd-length lists D Because Python evaluates assignments right to left
   pch.quizShowAnswer

   B — Because `first.next = second` destroys the pointer to the rest of the first list — you must save both successors before either assignment — Same assignment-order discipline as every rewiring problem: save what you are about to overwrite. Tuple assignment evaluates the whole right side first, which is what makes the one-liner safe.

6. For odd-length input the split gives the first half the extra node (1→2→3 vs 4→5). Does that matter?

   A No, either split works B Yes — it guarantees the first half is never shorter, which is what lets the interleave terminate on `while second` with no leftover-node special case C Yes, otherwise the result is reversed D It only matters for even lengths
   pch.quizShowAnswer

   B — Yes — it guarantees the first half is never shorter, which is what lets the interleave terminate on `while second` with no leftover-node special case — The fast/slow split produces that asymmetry naturally. Getting it the other way round forces an extra tail fix-up, which is where off-by-one bugs live.

Recall card

• Cue — a list problem that is not a single traversal: an extra pointer to clone, nested child lists to splice, or a permutation of the existing nodes.
• Copy with extras (LC 138) — two passes: create all clones into a dict, then wire next and random with clone.get(...). $O(1)$ space via the weave-then-unweave trick.
• Reorder (LC 143) — three composed techniques: fast/slow split (slow.next = None!), in-place reverse of the second half, then interleave.
• Flatten (LC 430) — splice each child list in where it was found: remember node.next, walk to the child list’s tail, join, and clear the child field.
• Every field must stay consistent — prev, child, random: a solution that fixes next and leaves a stale child passes a naive check and fails the real one.
• Save before overwriting, always naming successors first.
• Cost — all $O(n)$ time; the interview is about getting to $O(1)$ space.

Recap

• When a pointer can target a node that does not exist yet, create everything first and wire second — a dict from original to copy. Use .get() so None maps to None.
• The $O(1)$-space deep copy interleaves copies into the original list, making the list itself the map: orig.random.next is the copy of orig.random.
• Reorder List is a composition: find the middle, split, reverse the second half, interleave. The slow.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 — next, prev, and clearing child.
• 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.