{x}
blog image

Flatten a Multilevel Doubly Linked List

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

 

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 3:

Input: head = []
Output: []
Explanation: There could be empty list in the input.

 

Constraints:

  • The number of Nodes will not exceed 1000.
  • 1 <= Node.val <= 105

 

How the multilevel linked list is represented in test cases:

We use the multilevel linked list from Example 1 above:

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

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,    2,    3, 4, 5, 6, null]
             |
[null, null, 7,    8, 9, 10, null]
                   |
[            null, 11, 12, null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Solution Explanation

This problem asks to flatten a multilevel doubly linked list. The challenge lies in the presence of child pointers, which can lead to nested lists. The solution uses a recursive depth-first search (DFS) approach to traverse and flatten the list.

Approach:

The core idea is to recursively flatten each child list and then link it back into the main list. We use a helper function preorder (or flattenGetTail in C++) that does the following:

  1. Base Case: If the current node (cur) is null, it means we've reached the end of a branch, so we return the previous node (pre).

  2. Linking: Connect the previous node (pre) to the current node (cur) by setting pre.next = cur and cur.prev = pre.

  3. Recursive Call: Recursively call preorder to flatten the current node's child list. The result of this recursive call gives us the tail of the flattened child list.

  4. Connecting Child List: After flattening the child list, connect its tail to the next node in the original list (t).

  5. Null Child Pointer: Set the child pointer of the current node to null to ensure it points to nothing after flattening.

  6. Continuing: Continue iterating through the main list by moving to the next node.

Time Complexity Analysis:

The algorithm visits each node exactly once. The time complexity is directly proportional to the number of nodes in the list. Therefore, the time complexity is O(N), where N is the total number of nodes in the multilevel list.

Space Complexity Analysis:

The space complexity is determined by the maximum depth of the recursion stack. In the worst-case scenario, where the linked list is a very deep, unbalanced tree, the space complexity could be O(H), where H is the height of the multilevel linked list. In a balanced tree, H would be log(N), while in a skewed list, H could reach N. Therefore the space complexity is O(N) in the worst case.

Code Explanation (Python):

The Python code implements the preorder function recursively as described above. The main flatten function creates a dummy node at the beginning to simplify the handling of the head, then it calls preorder starting with the dummy node and the head node. Finally it adjusts the prev pointer of the actual head.

Code Explanation (Java):

The Java code mirrors the Python solution closely. The preorder function recursively flattens the list. A dummy node is used to handle the initial linking, and the prev pointer of the head node is adjusted after the flattening is done.

Code Explanation (C++):

The C++ solution uses an iterative approach within the flattenGetTail function which can be slightly more efficient than pure recursion for very large lists, although its time complexity remains the same. This helper function iterates through the list, and whenever it encounters a child list, it recursively calls itself to flatten the child list. The flattened child list is then integrated back into the main list by manipulating the next and prev pointers. The flatten function simply calls flattenGetTail to initiate the flattening process.

All three code examples achieve the same result, with minor variations in syntax and structure. The choice of language depends on personal preference and project requirements.