Flattening Doubly Linked List
Description
Flattening a doubly linked list involves converting a nested doubly linked list structure containing child lists, into a simple linear doubly linked list containing all the nodes from all the nested lists in order.
For example, a nested list:
Parent -> Child1 -> Child2
Would become:
Parent -> Child1[1] -> Child1[2] -> Child2[1] -> Child2[2]
Flattening simplifies traversal and access to all nodes across hierarchical lists in linear fashion.
Solution
Here is how a nested doubly linked list can be flattened:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /* Flattens given nested DLL */
Node flatten(Node head) {
// If empty list, return
if (head == null) {
return head;
}
// Create pointer to head node
Node ptr = head;
while (ptr.next != null) {
// If current node has child
if (ptr.child != null) {
// Make child next of current node
ptr.next.prev = ptr.child;
ptr.child.next = ptr.next;
// Connect current with child end
ptr.next = ptr.child;
ptr.child.prev = ptr;
// Set child to null
ptr.child = null;
}
ptr = ptr.next;
}
return head;
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /* Flattens given nested DLL */
Node* flatten(Node* head) {
if(head == NULL) return head;
Node* ptr = head;
while(ptr->next != NULL) {
if(ptr->child != NULL) {
ptr->next->prev = ptr->child;
ptr->child->next = ptr->next;
ptr->next = ptr->child;
ptr->child->prev = ptr;
ptr->child = NULL;
}
ptr = ptr->next;
}
return head;
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # Flattens given nested DLL
def flatten(head):
ptr = head
while ptr.next:
if ptr.child:
ptr.next.prev = ptr.child
ptr.child.next = ptr.next
ptr.next = ptr.child
ptr.child.prev = ptr
ptr.child = None
ptr = ptr.next
return head
|
This linearizes nested DLLs by grafting child nodes into the main list.
Description: Flattening Doubly Linked List
Flattening a Doubly Linked List means converting a multi-level doubly linked list into a simple one-level doubly linked list. In a multi-level doubly linked list, in addition to the regular next and previous pointers, each node also has a child
pointer that links to another doubly linked list. Flattening such a list involves expanding the child lists and combining them into a single list, maintaining the original order.
Solution:
The core idea for flattening is to traverse the list while integrating child lists wherever they appear. This can be achieved using a recursive approach or an iterative one.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Node {
int data;
Node next, prev, child;
Node(int data) {
this.data = data;
next = prev = child = null;
}
}
public class FlatteningList {
public static Node flatten(Node head) {
Node curr = head;
while (curr != null) {
if (curr.child != null) {
Node nextNode = curr.next;
curr.next = curr.child;
curr.child.prev = curr;
curr.child = null;
Node temp = curr.next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = nextNode;
if (nextNode != null) {
nextNode.prev = temp;
}
}
curr = curr.next;
}
return head;
}
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
struct Node {
int data;
Node* next;
Node* prev;
Node* child;
Node(int data) : data(data), next(nullptr), prev(nullptr), child(nullptr) {}
};
Node* flatten(Node* head) {
Node* curr = head;
while (curr != nullptr) {
if (curr->child != nullptr) {
Node* nextNode = curr->next;
curr->next = curr->child;
curr->child->prev = curr;
curr->child = nullptr;
Node* temp = curr->next;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = nextNode;
if (nextNode != nullptr) {
nextNode->prev = temp;
}
}
curr = curr->next;
}
return head;
}
int main() {
// Implementation details
return 0;
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Node:
def __init__(self, data):
self.data = data
self.next = self.prev = self.child = None
def flatten(head):
curr = head
while curr:
if curr.child:
next_node = curr.next
curr.next = curr.child
curr.child.prev = curr
curr.child = None
temp = curr.next
while temp.next:
temp = temp.next
temp.next = next_node
if next_node:
next_node.prev = temp
curr = curr.next
return head
|
Key Takeaways:
- Flattening a multi-level doubly linked list involves converting it into a simple doubly linked list.
- Each node has an additional
child
pointer, which is used to link to another doubly linked list. - You can use an iterative method to flatten the list, traversing the list and integrating child lists where they appear.
- You have to adjust the
next
and prev
pointers carefully while flattening to maintain the doubly linked list structure.