Flatten a Multilevel Doubly Linked List

You are given the head of a multilevel doubly linked list. In this list, nodes may have a child pointer to a separate doubly linked list. These child lists may themselves have children, forming multiple levels.

Flatten the list so that all nodes appear in a single-level doubly linked list. The nodes should appear in depth-first order (DFS) — when a node has a child, the child sublist is inserted between the node and its next sibling.

The input is encoded as a flat array using the LeetCode convention: non-null values are node values in order; a sequence of null values separates levels. The number of nulls before a child group indicates the 0-indexed position (minus 1) within the parent group where the child attaches.

Return the flattened list as an array of values in DFS order.

Examples

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,null,null,11,12]

Output: [1,2,3,7,8,11,12,4,5,6]

Explanation:

• Level 1: 1→2→3→4→5→6
• Node 3 (index 2) has child → Level 2: 7→8
• Node 8 (index 1 in its group) has child → Level 3: 11→12
• DFS order: 1, 2, 3, 7, 8, 11, 12, 4, 5, 6

Example 2:

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

Output: [1,3,2]

Explanation:

• Level 1: 1→2
• Node 1 (index 0) has child → Level 2: 3
• DFS order: 1, 3, 2

Example 3:

Input: head = []

Output: []

Explanation: Empty list returns empty.

Constraints

• The number of nodes in the list is in the range [0, 1000]
• 1 <= Node.val <= 10⁶
• The depth of the multilevel list is at most 1000