Flatten a Multilevel Doubly Linked List

Intuition

Flattening in depth-first order means that as soon as we meet a node with a child, the entire child list, fully flattened, must appear before we continue along the current level. We process one level with a loop, and whenever the current node owns a child we recurse to flatten that sublevel first. The recursive call returns the tail of the flattened child list, which is exactly the node we must connect back to the original successor. We rewire next and prev pointers on both the join between the node and its child head and the join between the child tail and the saved successor, then clear the child pointer. Returning the last node of a flattened level lets each parent frame stitch its sublist back together in constant time.

Algorithm walkthrough

1. 1If the head is null, return it directly since there is nothing to flatten.
2. 2Use a helper that scans the current level with a pointer, remembering next = curr.next before any rewiring.
3. 3When curr has a child, recursively flatten the child to obtain its tail, then set curr.next to the child head and the child head's prev back to curr, and clear curr.child.
4. 4If a saved next existed, connect the child tail to it by setting childTail.next = next and next.prev = childTail so the level continues after the inserted block.
5. 5Track the last node visited and return it so parent calls can splice, then finally return the original head.

Implementation

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return head

        def dfs(node):
            curr = node
            last = node
            while curr:
                nxt = curr.next
                if curr.child:
                    child_tail = dfs(curr.child)
                    curr.next = curr.child
                    curr.child.prev = curr
                    curr.child = None
                    if nxt:
                        child_tail.next = nxt
                        nxt.prev = child_tail
                    last = child_tail
                else:
                    last = curr
                curr = nxt
            return last

        dfs(head)
        return head