#430
Flatten a Multilevel Doubly Linked List
specialist · 675 · lc medium +30 · verified · 62.6% accepted · 5,445 likes · top 64%
Description
A doubly linked list has nodes that each carry next, prev, and child pointers. When child is non-null it points to another such doubly linked list, which may itself have children, forming a multi-level hierarchy.
Given the head of the top level, flatten the entire structure into a single-level doubly linked list. Every child list is spliced in immediately after its parent node (before the parent's former next). All child pointers must be set to null in the output.
Return the head of the resulting flat list.
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: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
Example 2:
Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
Example 3:
Input: head = []
Output: []
Explanation: There could be empty list in the input.
Example 4:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
Example 5:
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
Example 6:
[1, 2, 3, 4, 5, 6, null]
|
[null, null, 7, 8, 9, 10, null]
|
[ null, 11, 12, null]
Example 7:
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Code
1
2
3
4
5
6
7
8
9
10
11
12
13