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.