DSA problem
Flatten a Multilevel Doubly Linked List
You are given a doubly linked list in which, in addition to the next and prev pointers, each node has a child pointer that may point to a separate doubly linked list. These child lists may themselves have children, forming a multilevel data structure.
Your task is to flatten the list so that all nodes appear in a single-level doubly linked list. The flattened list should follow a depth-first order: when a node has a child, the entire child sublist (and recursively its descendants) must be inserted between that node and the node that originally followed it.
After flattening, every child pointer must be set to null, and the prev and next pointers must be correctly wired so the result is a valid doubly linked list. The relative order within each level is preserved; only the nesting is removed.
The optimal approach walks the list with a single pointer. Whenever the current node has a child, splice the child sublist directly between the node and its next, fixing the prev links and connecting the tail of the child chain back to the original successor. Clearing the child pointer and continuing the traversal naturally handles arbitrary nesting depth in O(n) time and O(1) extra space.
Examples
head = [1,2,3,4,5,6] with node 3 having child [7,8,9,10] and node 8 having child [11,12][1,2,3,7,8,11,12,9,10,4,5,6]head = [1,2] with node 1 having child [3][1,3,2]head = [][]Constraints
- The number of Nodes will not exceed 1000.
- 1 <= Node.val <= 100000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.