Advanced Open Free

Flatten a Multi-Level Linked List

You are given a doubly linked list where, in addition to the next and prev pointers, each node may have a child pointer to a separate doubly linked list. That child list may itself contain nodes with their own child pointers, nested to any depth. Flatten the list so that all nodes appear in a single-level doubly linked list, in depth-first order: whenever a node has a child, the entire child list (flattened) is spliced in immediately after that node and before its original next. After flattening, every child pointer must be set to None.

Input (top level, with a child list under node 3):
1 -> 2 -> 3 -> 4 -> 5 -> None
          |
          7 -> 8 -> None
               |
               9 -> None

Output (flattened, depth-first):
1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 4 -> 5 -> None

Example

Input:  head = 1 <-> 2 <-> 3 <-> None, with 2.child = 4 <-> 5 <-> None
Output: 1 <-> 2 <-> 4 <-> 5 <-> 3 <-> None

Constraints

The number of nodes across all levels is at most 1000.
child pointers may be None for most nodes.
Aim for O(n) time, visiting each node once.

Solution

This is a depth-first traversal problem disguised as a linked-list problem: whenever you hit a node with a child, you must fully flatten and splice in that child list before continuing to the original next. A clean iterative approach avoids deep recursion for long chains by using an explicit stack.

Walk the list with a curr pointer. Whenever curr.child is not None, that's a branch point: push curr.next onto a stack (to resume later), splice curr.child in as the new curr.next, fix up the prev pointers, and clear curr.child. When curr.next becomes None and the stack is non-empty, pop the next node to resume from there — this naturally continues the depth-first order because children are always fully explored before the stack gives back the node that was waiting after them.

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

def flatten(head: "Node | None") -> "Node | None":
    if head is None:
        return None

    stack = []
    curr = head

    while curr is not None:
        if curr.child is not None:
            if curr.next is not None:
                stack.append(curr.next)  # resume point, saved

            child = curr.child
            curr.next = child
            child.prev = curr
            curr.child = None  # clear the branch pointer

        elif curr.next is None and stack:
            next_node = stack.pop()
            curr.next = next_node
            next_node.prev = curr

        curr = curr.next

    return head

Complexity: O(n) time, since every node (across all nesting levels) is visited and relinked exactly once. O(d) extra space for the stack, where d is the maximum number of simultaneously pending "resume points" (bounded by the total number of nodes with a child in the worst case, so O(n) in the worst case, but typically much less).

Share this question

Share on X Share on LinkedIn

← Back to Linked Lists practice