Sponsored
Sponsored
In this approach, we utilize a stack to achieve depth-first traversal of the multilevel doubly linked list. We push nodes into the stack starting from the head, along with managing the child nodes as higher priority over next nodes. This ensures that we process all child nodes before moving on to the next nodes.
Time Complexity: O(n) where n is the number of nodes. Each node is visited once.
Space Complexity: O(n) for the stack in the worst case scenario.
1class Solution:
2 def flatten(self, head: 'Node') -> 'Node':
3 if not head:
4 return head
5
6 stack = []
7 curr = head
8
9 while curr:
10 if curr.child:
11 if curr.next:
12 stack.append(curr.next)
13 curr.next = curr.child
14 curr.next.prev = curr
15 curr.child = None
16
17 if not curr.next and stack:
18 curr.next = stack.pop()
19 if curr.next:
20 curr.next.prev = curr
21
22 curr = curr.next
23
24 return headThe Python solution employs a straightforward stack approach, easily manipulating the stack to remember and resume positions in the linked list after processing child nodes.
This approach utilizes recursion to handle the traversing and flattening of lists. By inherently using the function call stack, it efficiently manages shifts between the parent and child lists, automatically flattening the entire structure as it recursively resolves each node and its children.
Time Complexity: O(n) due to the necessity to visit each node once.
Space Complexity: O(d) where d is the maximum depth of the children, necessitating stack space for recursion.
The recursive C solution uses a helper function inside the primary function to handle recursive flattening, where each call processes and flattens the child list before linking back to the parent node’s next list.