Flatten a Multilevel Doubly Linked List
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.
Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.
Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.
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 a single level doubly linked list.
Clarifications:
- Can the input linked list be empty?
- What should happen if there are multiple layers of child linked lists?
- Are there any constraints on the size or values of the nodes in the linked list?
## Flattening a Multilevel Doubly Linked List
### Problem Description
You are given a doubly linked list where nodes can have a `next` pointer, a `previous` pointer, and a `child` pointer. The `child` pointer may or may not point to a separate doubly linked list, creating a multilevel data structure. The goal is to flatten this multilevel list into a single-level doubly linked list.
The nodes in the child list should appear after the current node and before the current node's `next` node in the flattened list. After flattening, all `child` pointers should be set to `null`.
**Example:**
Consider the following multilevel linked list:
1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL
The flattened list should be:
1---2---3---7---8---11---12---9---10---4---5---6--NULL
### Naive Approach
A simple approach is to traverse the linked list and, whenever a child is encountered, recursively flatten the child list and insert it into the main list. This can be done using depth-first search (DFS).
### Optimal Solution
The optimal approach also uses DFS but performs the flattening in place to avoid extra memory usage. We can traverse the list, and whenever a child node is found, we:
1. Detach the child list.
2. Find the tail of the child list.
3. Insert the child list between the current node and the next node.
4. Set the child pointer to `null`.
Here's the code in Python:
```python
class Node:
def __init__(self, val, prev=None, next=None, child=None):
self.val = val
self.prev = prev
self.next = next
self.child = child
def flatten(head: 'Node') -> 'Node':
if not head:
return head
def flatten_dfs(node: 'Node') -> 'Node':
curr = node
tail = node
while curr:
if curr.child:
child_head = curr.child
child_tail = flatten_dfs(child_head)
# Connect child list
next_node = curr.next
curr.next = child_head
child_head.prev = curr
# Connect tail to next node
if next_node:
child_tail.next = next_node
next_node.prev = child_tail
# Remove child pointer
curr.child = None
curr = next_node # Continue from the original next node
else:
tail = curr
curr = curr.next
return tail
flatten_dfs(head)
return head
Example Usage:
# Create the linked list: 1-2-3-4-5-6-null
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
node4.next = node5
node5.prev = node4
node5.next = node6
node6.prev = node5
# Create the child list: 7-8-9-10-null
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
node10 = Node(10)
node7.next = node8
node8.prev = node7
node8.next = node9
node9.prev = node8
node9.next = node10
node10.prev = node9
# Create the child list: 11-12-null
node11 = Node(11)
node12 = Node(12)
node11.next = node12
node12.prev = node11
# Connect the child lists
node3.child = node7
node8.child = node11
head = node1
flattened_head = flatten(head)
# Print the flattened list
curr = flattened_head
while curr:
print(curr.val, end=" " if curr.next else "\n")
curr = curr.next
Big(O) Run-time Analysis
The algorithm traverses each node in the multilevel linked list exactly once. Therefore, the time complexity is O(N), where N is the total number of nodes in the flattened list.
Big(O) Space Usage Analysis
The algorithm operates in place and uses a recursive approach for flattening. In the worst case, the recursion depth can be equal to the maximum depth of the multilevel list. However, since the problem constraints specify that the number of nodes will not exceed 1000, the maximum recursion depth is limited. Therefore, the space complexity is O(D), where D is the depth of the multilevel linked list, but in the worst-case it can be said that it is O(1) because the maximum depth is constrained to be very small.
Edge Cases
- Empty List: If the input list is empty (
headisNone), the function should returnNone. - No Children: If none of the nodes have children, the function should return the original list.
- Deeply Nested Children: The algorithm should handle deeply nested child lists correctly by recursively flattening them.
- Multiple Child Nodes: If a node has multiple children (which is not part of the original problem statement but a good test), the algorithm should only consider the first child.
These cases are handled in the provided code by:
- Returning early if
headisNone. - Traversing each node and checking for a child before proceeding.
- Recursively flattening child lists.
This approach ensures correctness and efficiency for flattening multilevel linked lists.
