350. Flatten a Multilevel Doubly Linked List
You are given the head of a doubly linked list whose nodes carry four fields: an integer val, the usual prev and next pointers, and an extra child pointer. A child pointer either is null or references the head of another doubly linked list of the same kind — and those child lists may have children of their own, nesting to any depth.
Flatten everything into a single-level doubly linked list and return its head. The required order: each node's child list is spliced in between the node and its next node, and a child list is fully flattened before it is spliced. After flattening, every child pointer must be null, all prev/next links must agree in both directions, and the head's prev must be null.
The grader walks next pointers from the node you return, verifying each prev back-link and that no child pointer survives; it prints the values in order, or invalid if the structure is broken.
Example 1:
Input: head = 1-2-3-4-5-6, with 3.child = 7-8-9-10 and 8.child = 11-12
Output: head of 1-2-3-7-8-11-12-9-10-4-5-6
Explanation: The child list of 3 is spliced between 3 and 4 — but first that child list is itself flattened, so 11-12 slots in between 8 and 9.
Example 2:
Input: head = 1-2, with 1.child = 3
Output: head of 1-3-2
Explanation: Node 1's child list [3] goes between 1 and its next node 2.
Constraints:
- 1 ≤ total number of nodes ≤ 1000
- 1 ≤ Node.val ≤ 10⁵
- Child lists may nest to a depth of up to 100.
Hints:
The flattened order is a depth-first walk: a node, then its entire child list (already flattened), then the node's next. Recursion or an explicit stack produces exactly that order.
There is also an O(1)-memory version: walk the list, and whenever the current node has a child, find the child list's tail and splice the whole child list between the node and its next — nested children get handled later, when the walk reaches them.
Two housekeeping details the checker verifies: every child pointer must end up null, and every splice must repair prev links in both directions.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: 1-2-3-4-5-6, 3.child = 7-8-9-10, 8.child = 11-12
Expected output: 1-2-3-7-8-11-12-9-10-4-5-6