Linked List - Flatten a Multilevel Doubly Linked List

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

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.

Input: head = [1,2,null,3]
Output: [1,3,2]

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

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)