Flatten a Multilevel Doubly Linked List

Share

A doubly linked list where nodes may have a child pointer to another doubly linked list. Flatten it so all nodes appear in a single-level doubly linked list (depth-first).

Example 1
Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: Depth-first: follow child before continuing next.
Example 2
Input: head = [1,2,null,3]
Output: [1,3,2]

Solution Approach

Iterate with a stack. When a child is encountered, push the next node onto a stack, then follow the child. When current.next is null, pop from stack if available.

  • Iterative: when node.child != null, insert child list between node and node.next
  • Find tail of child list, connect to node.next
Java
public Node flatten(Node head) {
    if (head == null) return null;
    Node curr = head;
    while (curr != null) {
        if (curr.child != null) {
            Node child = curr.child, next = curr.next;
            curr.next = child; child.prev = curr; curr.child = null;
            Node tail = child;
            while (tail.next != null) tail = tail.next;
            tail.next = next;
            if (next != null) next.prev = tail;
        }
        curr = curr.next;
    }
    return head;
}
Complexity Analysis:

Time complexity: O(n)
Space complexity: O(1)