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.
1#include <stdlib.h>
2
3struct Node {
4 int val;
5 struct Node* next;
6 struct Node* prev;
7 struct Node* child;
8};
9
10struct Node* flatten(struct Node* head) {
11 if (!head) return head;
12 struct Node* ptr = head;
13 struct Node* stack[1000];
14 int top = -1;
15
16 while (ptr) {
17 if (ptr->child) {
18 if (ptr->next) {
19 stack[++top] = ptr->next;
20 }
21 ptr->next = ptr->child;
22 ptr->next->prev = ptr;
23 ptr->child = NULL;
24 } else if (!ptr->next && top != -1) {
25 ptr->next = stack[top--];
26 if (ptr->next) {
27 ptr->next->prev = ptr;
28 }
29 }
30 ptr = ptr->next;
31 }
32
33 return head;
34}The C solution employs a stack data structure to manage the traversal of the multilevel doubly linked list. We start at the head and check if there's a child. If there is, we push the next pointer, set the child as the next node, and nullify the child. If we encounter the end of a list and have stored nodes in the stack, we pop one to continue.
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.
1 public Node Flatten(Node head) {
if (head == null) return head;
FlattenDFS(head);
return head;
}
private Node FlattenDFS(Node node) {
Node curr = node;
Node tail = node;
while (curr != null) {
Node nextNode = curr.next;
if (curr.child != null) {
Node childTail = FlattenDFS(curr.child);
curr.next = curr.child;
curr.child.prev = curr;
curr.child = null;
if (nextNode != null) {
childTail.next = nextNode;
nextNode.prev = childTail;
}
tail = childTail;
} else {
tail = curr;
}
curr = nextNode;
}
return tail;
}
}The C# solution utilizes a recursive strategy with `FlattenDFS` to traverse through nodes, methodically converting multilevel lists into singular level entities, handling pointers between list levels smoothly over recursive detail management.