Flatten a Multilevel Linked List

A multilevel linked list is a doubly linked list where some nodes have a child pointer leading to another doubly linked list, which itself may have children. Think of it like a nested outline — headings with sub-points, which have their own sub-points. Flattening means collapsing all these levels into a single-level list.

This problem appears frequently in interviews because it tests your ability to handle complex pointer manipulation with a clear strategy. The key insight: flattening a multilevel list is essentially a depth-first traversal.

---

Problem 1: Flatten multilevel doubly linked list (LeetCode 430)

Problem statement

You are given a doubly linked list where each node has next, prev, and child pointers. Flatten the list so that all nodes appear in a single-level, doubly linked list. The child lists should be inserted between the current node and its next node.

LeetCode 430 — Flatten a Multilevel Doubly Linked List

Node definition

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

Visual example

Input (multilevel structure):

Level 1:  1 --- 2 --- 3 --- 4 --- 5 --- 6
                      |
Level 2:              7 --- 8 --- 9 --- 10
                            |
Level 3:                    11 --- 12

Output (flattened):
1 - 2 - 3 - 7 - 8 - 11 - 12 - 9 - 10 - 4 - 5 - 6

The rule: when you encounter a child, insert the entire child
chain before continuing with the current level's next node.

Why this is DFS

When node 3 has a child (node 7), we go deeper before going across. When node 8 has a child (node 11), we go deeper again. Only after exhausting a child chain do we return to the parent level. This is textbook depth-first search.

---

Approach 1: Iterative with a stack

Intuition

Use a stack to remember “where to come back to” after processing a child chain. When we encounter a node with a child:

1. Push node.next onto the stack (we’ll come back to it).
2. Set node.next = node.child and update prev pointers.
3. Clear node.child.

When we reach the end of a chain (a node with no next and no child), pop from the stack to continue with the saved next node.

Implementation

def flatten_iterative(head: 'Node') -> 'Node':
    if not head:
        return head

    stack = []
    current = head

    while current:
        # If this node has a child, process it
        if current.child:
            # Save the next node for later (if it exists)
            if current.next:
                stack.append(current.next)

            # Connect current to child
            current.next = current.child
            current.child.prev = current
            current.child = None  # Clear the child pointer

        # If we've reached the end of a chain and stack has saved nodes
        if not current.next and stack:
            next_node = stack.pop()
            current.next = next_node
            next_node.prev = current

        current = current.next

    return head

Step-by-step walkthrough

Start: 1 - 2 - 3(child:7) - 4 - 5 - 6
Stack: []

At node 1: no child, move to 2
At node 2: no child, move to 3

At node 3: has child (7)
  Push 4 onto stack.  Stack: [4]
  Set 3.next = 7, 7.prev = 3, 3.child = None
  Now: 1 - 2 - 3 - 7 - 8(child:11) - 9 - 10
                                              Stack: [4]

At node 7: no child, move to 8

At node 8: has child (11)
  Push 9 onto stack.  Stack: [4, 9]
  Set 8.next = 11, 11.prev = 8, 8.child = None
  Now: ... 7 - 8 - 11 - 12
                          Stack: [4, 9]

At node 11: no child, move to 12

At node 12: no child, no next
  Pop 9 from stack.  Stack: [4]
  Set 12.next = 9, 9.prev = 12
  Now: ... 11 - 12 - 9 - 10
                           Stack: [4]

At node 9: no child, move to 10

At node 10: no child, no next
  Pop 4 from stack.  Stack: []
  Set 10.next = 4, 4.prev = 10
  Now: ... 9 - 10 - 4 - 5 - 6

At nodes 4, 5, 6: no children, traverse to end

Final: 1 - 2 - 3 - 7 - 8 - 11 - 12 - 9 - 10 - 4 - 5 - 6

Complexity

Metric	Value
Time	O(n) — each node visited once
Space	O(n) worst case — stack could hold nodes from each level

---

Approach 2: Recursive DFS

Intuition

Recursively flatten each child chain, then splice the flattened chain into the current level. The recursive function returns the tail of the flattened portion, which is useful for connecting back to the parent level.

Implementation

def flatten_recursive(head: 'Node') -> 'Node':
    if not head:
        return head

    def flatten_dfs(node):
        """
        Flatten starting from node.
        Returns the tail of the flattened list.
        """
        current = node
        tail = node

        while current:
            next_node = current.next

            if current.child:
                # Recursively flatten the child chain
                child_tail = flatten_dfs(current.child)

                # Connect current -> child
                current.next = current.child
                current.child.prev = current

                # Connect child_tail -> next_node
                if next_node:
                    child_tail.next = next_node
                    next_node.prev = child_tail

                # Clear child pointer
                current.child = None

                # Update tail to child_tail (or further)
                tail = child_tail
            else:
                tail = current

            current = next_node

        return tail

    flatten_dfs(head)
    return head

How the recursion unfolds

flatten_dfs(1):
  At 1: no child
  At 2: no child
  At 3: has child (7)
    flatten_dfs(7):
      At 7: no child
      At 8: has child (11)
        flatten_dfs(11):
          At 11: no child
          At 12: no child, no next
          Returns tail = 12
      
      Connect: 8 -> 11 ... 12 -> 9
      At 9: no child
      At 10: no child, no next
      Returns tail = 10
    
    Connect: 3 -> 7 ... 10 -> 4
  At 4: no child
  At 5: no child
  At 6: no child, no next
  Returns tail = 6

Complexity

Metric	Value
Time	O(n) — each node visited once
Space	O(d) where d is the maximum depth of nesting (recursion stack)

---

Problem 2: Flatten sorted linked lists

A different flavor of “flatten” appears when you have a list of sorted linked lists and need to merge them into one sorted list. Each node has a next pointer for the main list and a down pointer for the sub-list.

Node definition

class SortedNode:
    def __init__(self, val=0, next=None, down=None):
        self.val = val
        self.next = next   # Points to the next list head
        self.down = down    # Points down within the same list

Visual example

5  -> 10 -> 19 -> 28
|     |     |     |
7     20    22    35
|           |     |
8           50    40
|                 |
30                45

Flattened (sorted): 5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 28 -> 30 -> 35 -> 40 -> 45 -> 50

Approach: Merge from right to left

Merge the last two lists, then merge the result with the third-to-last, and so on. This is similar to merge sort’s merge step.

def merge_two_lists(a: SortedNode, b: SortedNode) -> SortedNode:
    """Merge two sorted lists connected by 'down' pointers."""
    dummy = SortedNode(0)
    current = dummy

    while a and b:
        if a.val {'<'}= b.val:
            current.down = a
            a = a.down
        else:
            current.down = b
            b = b.down
        current = current.down

    current.down = a if a else b

    return dummy.down


def flatten_sorted_lists(head: SortedNode) -> SortedNode:
    """
    Flatten a list of sorted linked lists into one sorted list.
    Lists are connected by 'next' at the head level and 'down' within.
    """
    if not head or not head.next:
        return head

    # Recursively flatten from the right
    head.next = flatten_sorted_lists(head.next)

    # Merge current list with the flattened result
    head = merge_two_lists(head, head.next)

    return head

Walkthrough

Step 1: Merge list 4 (28,35,40,45) with nothing => [28,35,40,45]
Step 2: Merge list 3 (19,22,50) with [28,35,40,45]
  => [19,22,28,35,40,45,50]
Step 3: Merge list 2 (10,20) with [19,22,28,35,40,45,50]
  => [10,19,20,22,28,35,40,45,50]
Step 4: Merge list 1 (5,7,8,30) with [10,19,20,22,28,35,40,45,50]
  => [5,7,8,10,19,20,22,28,30,35,40,45,50]

Complexity

Metric	Value
Time	O(n * k) where n is total nodes and k is number of lists (worst case)
Space	O(k) recursion depth for k lists

For a more efficient approach with many lists, use a min-heap — see LeetCode 23 (Merge k Sorted Lists).

---

Iterative vs recursive comparison

Aspect	Iterative (stack)	Recursive (DFS)
Readability	Clear step-by-step flow	Elegant but harder to trace
Space	O(n) worst case (explicit stack)	O(d) where d = nesting depth
Stack overflow risk	None	Yes, for deeply nested lists
Interview preference	Good for showing you can manage state	Good for showing DFS thinking

Both approaches are valid in interviews. The iterative approach is generally safer (no stack overflow risk) and easier to debug, while the recursive approach is more concise.

---

Common mistakes

1. Forgetting to set prev pointers. In a doubly linked list, every next connection needs a corresponding prev connection. Missing prev pointers cause bugs in backward traversal.

2. Not clearing the child pointer. After splicing a child chain into the main list, set node.child = None. The problem requires all child pointers to be null in the output.

3. Losing the next pointer. When you redirect current.next to current.child, save current.next first. Otherwise you lose the rest of the main-level chain.

4. Not returning the tail in recursive approach. The recursive helper must return the tail so the parent call can connect the child chain’s end to the saved next node.

5. Confusing the two flatten problems. The multilevel DLL flatten (LeetCode 430) uses DFS ordering. The sorted lists flatten uses merge. Don’t mix up the strategies.

---

Testing your implementation

def build_test_case():
    """Build the example: 1-2-3-4-5-6 with child at 3 (7-8-9-10) and child at 8 (11-12)"""
    nodes = {i: Node(i) for i in range(1, 13)}

    # Level 1: 1-2-3-4-5-6
    for i in range(1, 6):
        nodes[i].next = nodes[i + 1]
        nodes[i + 1].prev = nodes[i]

    # Level 2: 7-8-9-10 as child of 3
    nodes[3].child = nodes[7]
    for i in range(7, 10):
        nodes[i].next = nodes[i + 1]
        nodes[i + 1].prev = nodes[i]

    # Level 3: 11-12 as child of 8
    nodes[8].child = nodes[11]
    nodes[11].next = nodes[12]
    nodes[12].prev = nodes[11]

    return nodes[1]


def print_list(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" - ".join(vals))


# Test
head = build_test_case()
result = flatten_iterative(head)
print_list(result)
# Output: 1 - 2 - 3 - 7 - 8 - 11 - 12 - 9 - 10 - 4 - 5 - 6

---

Practice problems

Problem	Difficulty	Link
Flatten a Multilevel Doubly Linked List	Medium	LeetCode 430
Flatten Binary Tree to Linked List	Medium	LeetCode 114
Merge k Sorted Lists	Hard	LeetCode 23
Merge Two Sorted Lists	Easy	LeetCode 21
Linked List in Binary Tree	Medium	LeetCode 1367

Key takeaways

• Flattening a multilevel list is DFS. Whether you implement it with an explicit stack or recursion, the core idea is: go deep (follow children) before going wide (follow next).
• Save before you overwrite. The most common bug in pointer manipulation problems is losing a reference. Always save node.next before redirecting it.
• Return the tail from recursive helpers. When flattening recursively, the parent call needs to know where the flattened child chain ends so it can reconnect the rest of the list.
• The dummy node trick works here too. For the sorted-list merge, a dummy simplifies the merge logic by eliminating the “which node is the new head?” decision.