Problem

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure.

Your task is to flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example

Consider the following multilevel doubly linked list:

1
2
3 1---2---3---4---5---6--NULL
4         |
5         7---8---9---10--NULL
6             |
7             11--12--NULL

We can flatten this list to form the following singly doubly linked list:

1
2
31-2-3-7-8-11-12-9-10-4-5-6-NULL

Approach

The idea is to use Depth First Search (DFS) to traverse through each level of nodes in the doubly linked list.

We start with the head of the list and continue to the next node, using DFS. When we encounter a node with a child, we recursively flatten the child list and then proceed to the next node. In the end, we attach the rest of the originally next nodes to the end of the flattened list.

Python Solution

1
2python
3class Solution:
4    def flatten(self, head, rest = None):
5        if head is None:
6            return rest
7
8        head.next = self.flatten(head.child, self.flatten(head.next, rest))
9        
10        if(head.next is not None):
11            head.next.prev = head
12        head.child = None
13        return head

Java Solution

1
2java
3class Solution {
4    public Node flatten(Node head) {
5        return dfs(head, null);
6    }
7
8    private Node dfs(Node head, Node rest) {
9        if (head == null)
10            return rest;
11
12        head.next = dfs(head.child, dfs(head.next, rest));
13
14        if (head.next != null)
15            head.next.prev = head;
16        head.child = null;
17        return head;
18    }
19}

Javascript Solution

1
2javascript
3class Solution {
4    flatten(head, rest = null)  {
5        if (head === null)
6            return rest;
7
8        head.next = this.flatten(head.child, this.flatten(head.next, rest));
9        
10        if(head.next !== null)
11            head.next.prev = head;
12        head.child = null;
13        return head;
14    }
15}

C++ Solution

1
2cpp
3class Solution {
4public:
5    Node* flatten(Node* head, Node* rest = nullptr)  {
6        if (head == nullptr)
7            return rest;
8
9        head->next = flatten(head->child, flatten(head->next, rest));
10        
11        if(head->next)
12            head->next->prev = head;
13        head->child = nullptr;
14        return head;
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public Node Flatten(Node head, Node rest = null) {
5        if (head == null)
6            return rest;
7
8        head.next = Flatten(head.child, Flatten(head.next, rest));
9        
10        if(head.next != null)
11            head.next.prev = head;
12        head.child = null;
13        return head;
14    }
15}

In these solutions, we are passing the rest of the list as a parameter to the flatten function. This allows us to flatten each list and then attach the rest of the original list at the end. This solution has a time complexity of O(n) and a space complexity of O(1) as it does not require additional space and visits each node once.# Conclusion

The challenge of flattening a multi-level doubly linked list can be solved with a depth-first search (DFS) approach. By iterating over each node, if a child node is found, the function is called recursively on the child, flattening all its decedents before returning to the parent level list. The recursive nature of DFS allows us to handle any depth of child nodes within the doubly linked list. This algorithm is efficient, with a time complexity of O(N), visiting each node once, and a space complexity of O(1), as it only requires a constant amount of space.

In conclusion, this problem showcases the utility and efficiency of the DFS algorithm in the process of flattening multi-level data structures. By understanding the underlying principles of DFS, we are not only able to navigate complex structures but also manipulate them, enabling more optimized and simplified data access and manipulation. The provided Python, JavaScript, C++, C# and Java solutions demonstrate the implementation of this approach.