430. Flatten a Multilevel Doubly Linked List

MediumDepth-First SearchLinked ListDoubly-Linked List
Leetcode Link

Problem Description

You are provided with a doubly linked list where each node contains the following pointers:

  • next pointing to the next node in the same level.
  • prev pointing to the previous node in the same level.
  • child potentially pointing to the head of another doubly linked list which represents a lower level.

These child pointers can create a multilevel doubly linked list structure. Different nodes at the same level may have child pointers leading to separate doubly linked lists, and this can continue across multiple levels.

The objective is to transform this multilevel doubly linked list into a single-level doubly linked list. To do so, we have to flatten the list, ensuring that any node's children (and their subsequent descendants) will be inserted in the list directly after the node and before the node's next sibling.

After the list is flattened, no node should have a child pointer; all child pointers must be set to null. The function should return the head of the flattened list.

Intuition

The intuition behind the solution lies in traversing the multilevel doubly linked list and restructuring it without using additional space (except for recursion stack). This can be achieved using a depth-first search-like approach. Here’s the intuition step by step:

  1. Use a depth-first search (DFS) approach that starts from the head and explores as far as possible along each branch before backtracking.
  2. Create a nested function (like preorder) to use for recursion, maintaining the current node and its previous node as parameters to wire the pointers correctly.
  3. As you traverse the list, when encountering a child node, recursively process the child list first and then continue with the next nodes, thereby flattening the list in place.
  4. Sever the link between the current node and its child after flattening the child list, ensuring all child pointers are set to null.
  5. Utilize the fact that in a doubly linked list, each node has a reference to both its previous and next nodes. Make sure that, after flattening, nodes still maintain proper references to their next and prev nodes.
  6. The recursion continues until there are no children nor next nodes to process, at which point the list is fully flattened.
  7. Use a dummy node to handle corner cases such as when the head node has a child; this simplifies the process of connecting the nodes.
  8. After flattening, disconnect the dummy head from the actual head and return the flattened list without the dummy.

Using this process, we incrementally build the flattened list by connecting sibling nodes and inserting child nodes appropriately, maintaining all the necessary connections both to preceding and following nodes.

Learn more about Depth-First Search and Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The solution provided uses a recursive approach to flatten the multilevel doubly linked list in place. Here is an explanation of the algorithm, which details how it operates on the doubly linked list structure:

  1. Recursive Preorder Traversal: The solution approach uses a depth-first search strategy reminiscent of the preorder traversal in tree data structures. A preorder traversal visits a node first, then its children, and then its siblings. The function preorder(pre, cur) where pre is the previous node, and cur is the current node, is designed to leverage this.

  2. Initialization with a Dummy Node: A dummy node is created with value "0," and it precedes the head of the list. This is useful to easily return the new head of the flattened list and to handle corner cases easily, such as when the head node itself has a child.

  3. Recursive Connection of Nodes: The preorder function recursively connects the nodes as follows:

    • If the current node (cur) is None, the end of a branch has been reached, and the function returns pre as the tail.
    • The current node cur is connected to the previous node pre by updating cur.prev and pre.next.
    • The recursion saves the next node of cur in a temporary variable t because the next pointer might change when processing the child nodes.
    • Recursively call preorder(cur, cur.child) to process and flatten any child list starting from the current node.
    • The connection to the child node is severed by setting cur.child to None after it's processed, thus flattening this current section.
    • Recursively call preorder(tail, t) using the last processed node (tail) from the child list and the saved next node (t). This continues flattening the rest of the list after the child list.

  4. Flatten the Whole List: The initial call preorder(dummy, head) starts the recursive processing of the list. The dummy node temporarily holds the place before the head node of the original list.

  5. Finishing Touches: After the entire list is flattened, the next pointer of the dummy node points to the new head of the flattened list. The previous pointer of the new head node (which is dummy.next), however, needs to be set to None because the dummy is not part of the actual list.

  6. Return the Flattened List: Finally, the new head of the flattened list is returned by dummy.next, excluding the dummy node from the final result.

Through this recursive process, the list is transformed in place. End-to-end, this means that child lists are integrated between their parent and the subsequent nodes, resulting in a properly flattened list that respects the original order and respects the doubly linked list property that each node should reference its previous and next siblings appropriately.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Consider the following multilevel doubly linked list as an example:

11 <-> 2 <-> 3 <-> 4
2       |
3       5 <-> 6 <-> 7
4             |
5             8

In this example, node 2 has a child doubly linked list starting with node 5, and node 6 also has a child doubly linked list starting with node 8.

Now let's flatten this list using the recursive approach described:

  1. Initialize the dummy node as the prev to the head of the list. Start flattening with preorder(dummy, head) where head is node 1. At this step, dummy.next will point to node 1.

  2. Using the preorder function, start the recursion with node 1 (head). Since node 1 has no children, it connects directly to node 2. The function proceeds to node 2.

  3. At node 2, a child list starts with node 5. Call preorder recursively to process this child list:

    • Node 5 is connected to node 2 before the preorder of the child list is initiated.
    • Node 5's child list (5 -> 6 -> 7) is processed fully. Node 6 is checked and found to have a child node 8.
    • Recursively process node 8 and connect it after node 6, flattening the child list further. Now the child list is (5 -> 6 -> 8 -> 7), which is connected to node 2.

  4. After flattening the list starting at node 5, node 2's child pointer is set to null, and we are left with a partial flat list:

11 <-> 2 <-> 5 <-> 6 <-> 8 <-> 7
2             |         |
3            null       null

  1. The recursion process returns to node 2 and continues with node 3, connecting node 7 to node 3, and so on until all nodes are processed linearly.

  2. After recursive calls have been executed for all nodes, we have a completely flattened list:

11 <-> 2 <-> 5 <-> 6 <-> 8 <-> 7 <-> 3 <-> 4

  1. Now, as per the final steps of the algorithm, adjust the linkage so that the dummy node is removed from the list, ensuring the new head's previous pointer (head.prev) is set to None.

  2. Return the new head of the flattened list, which is at first node 1 in our example.

Through these steps, we flatten the multilevel doubly linked list into a single-level doubly linked list in place without the use of additional space (other than the recursion stack).

Solution Implementation

1# Definition for a Node.
2class Node:
3    def __init__(self, val, prev=None, next=None, child=None):
4        self.val = val
5        self.prev = prev
6        self.next = next
7        self.child = child
8
9
10class Solution:
11    def flatten(self, head: 'Node') -> 'Node':
12        # Helper function to perform a preorder traversal and flatten the list.
13        def flatten_list(prev_node, current_node):
14            # Base case: if the current node is None, return the previous node.
15            if current_node is None:
16                return prev_node
17
18            # Connect the current node to the previous node in the flattened list.
19            current_node.prev = prev_node
20            prev_node.next = current_node
21
22            # Save the next node to continue traversal after the child nodes.
23            next_node = current_node.next
24
25            # Recursively flatten the child nodes.
26            tail = flatten_list(current_node, current_node.child)
27            # After flattening child nodes, the current node's child is set to None.
28            current_node.child = None
29
30            # Continue flattening with the saved next node.
31            return flatten_list(tail, next_node)
32
33        # If the head is None, there is nothing to flatten.
34        if head is None:
35            return None
36
37        # Create a dummy node to act as the starting point of the flattened list.
38        dummy = Node(0)
39        # Call the helper function to start flattening with the head node.
40        flatten_list(dummy, head)
41        # Disconnect the dummy node from the resulting flattened list and return it.
42        dummy.next.prev = None
43        return dummy.next
44
1class Solution {
2    // Method to flatten a multilevel doubly linked list.
3    public Node flatten(Node head) {
4        // If the list is empty, return null.
5        if (head == null) {
6            return null;
7        }
8      
9        Node dummyHead = new Node();  // Dummy head to simplify edge case management.
10        dummyHead.next = head;
11        flattenList(dummyHead, head); // Flatten the list starting from 'head'.
12        dummyHead.next.prev = null;   // Detach the dummy head from the real head of the list.
13      
14        return dummyHead.next;        // Return the flattened list without the dummy head.
15    }
16
17    // Helper method to recursively flatten the list.
18    // It connects the previous node ('prev') with the current node ('curr') and flattens the child lists.
19    private Node flattenList(Node prev, Node curr) {
20        if (curr == null) {
21            // If we reach the end of a list segment, return the last node that was encountered (prev).
22            return prev;
23        }
24      
25        curr.prev = prev;  // Connect the current node to the previous one.
26        prev.next = curr;
27
28        Node tempNext = curr.next;  // Temporarily store the next node.
29        Node tail = flattenList(curr, curr.child); // Flatten the child list.
30        curr.child = null;  // Clear the child pointer since it's now included in the flattened list.
31      
32        // Continue flattening from the end of the flattened child list and the next node after 'curr'.
33        return flattenList(tail, tempNext);
34    }
35}
36
1// The Node structure definition remains the same with the 'val', 'prev', 'next', and 'child' pointers.
2class Node {
3public:
4    int val;
5    Node* prev;
6    Node* next;
7    Node* child;
8};
9
10class Solution {
11public:
12    // The 'flatten' function is the entry point to flatten the multilevel doubly linked list.
13    Node* flatten(Node* head) {
14        // Start the flatten process and ignore the tail returned by helper function.
15        flattenAndGetTail(head);
16        return head; // Return the modified list with all levels flattened.
17    }
18
19    // Helper function which flattens the list and returns the tail node of the flattened list.
20    Node* flattenAndGetTail(Node* head) {
21        Node* current = head; // Pointer to traverse the list.
22        Node* tail = nullptr; // Pointer to keep track of the tail node.
23
24        while (current) {
25            Node* nextNode = current->next; // Store the next node of the current node.
26          
27            // If the current node has a child, we need to process it.
28            if (current->child) {
29                Node* childNode = current->child; // The child node which needs to be flattened.
30                Node* childTail = flattenAndGetTail(current->child); // Flatten the child list and get its tail.
31
32                current->child = nullptr; // Unlink the child from the current node.
33                current->next = childNode; // Make the current node point to the child node.
34                childNode->prev = current; // The child node's previous should now point back to the current node.
35                childTail->next = nextNode; // Connect the tail of the child list to the next node.
36
37                // If the next node is not null, adjust its previous pointer accordingly.
38                if (nextNode)
39                    nextNode->prev = childTail;
40
41                tail = childTail; // The new tail is the tail of the flattened child list.
42            } else {
43                tail = current; // If there's no child, the current node is the new tail.
44            }
45
46            current = nextNode; // Move to the next node in the list.
47        }
48
49        return tail; // Return the tail node of the flattened list.
50    }
51};
52
1// Node type definition with 'val', 'prev', 'next', and 'child' properties.
2type Node = {
3    val: number;
4    prev: Node | null;
5    next: Node | null;
6    child: Node | null;
7};
8
9// Entry function to flatten the multilevel doubly linked list.
10function flatten(head: Node | null): Node | null {
11    // Start the flatten process and ignore the tail returned by the helper function.
12    flattenAndGetTail(head);
13    return head; // Return the modified list with all levels flattened.
14}
15
16// Helper function which flattens the list and returns the tail node of the flattened list.
17function flattenAndGetTail(head: Node | null): Node | null {
18    let current: Node | null = head; // Pointer to traverse the list.
19    let tail: Node | null = null; // Pointer to keep track of the tail node.
20
21    while (current) {
22        let nextNode: Node | null = current.next; // Store the next node of the current node.
23
24        // If the current node has a child, we need to process it.
25        if (current.child) {
26            let childNode: Node = current.child; // The child node which needs to be flattened.
27            let childTail: Node | null = flattenAndGetTail(current.child); // Flatten the child list and get its tail.
28
29            current.child = null; // Unlink the child from the current node.
30            current.next = childNode; // Make the current node point to the child node.
31            childNode.prev = current; // The child node's previous should now point back to the current node.
32
33            if (childTail) {
34                childTail.next = nextNode; // Connect the tail of the child list to the next node.
35            }
36
37            // If the next node is not null, adjust its previous pointer accordingly.
38            if (nextNode) {
39                nextNode.prev = childTail;
40            }
41
42            tail = childTail; // The new tail is the tail of the flattened child list.
43        } else {
44            tail = current; // If there's no child, the current node is the new tail.
45        }
46
47        current = nextNode; // Move to the next node in the list.
48    }
49
50    return tail; // Return the tail node of the flattened list.
51}
52
Not Sure What to Study? Take the 2-min Quiz：

Which type of traversal does breadth first search do?

Time and Space Complexity

The given code performs a flattening operation on a doubly linked list with child pointers, which may point to separate doubly linked list nodes, effectively creating a multilevel doubly linked list.

Time Complexity:

The preorder() function used in the code traverses each node exactly once. The traversal involves visiting each node's next and child pointer if present. No node is visited more than once because as we visit a node with a child, we nullify the child pointer after processing.

Hence, if there are n total nodes in the multilevel linked list, each node will be visited only once. This means that the time complexity of the preorder traversal is O(n).

Space Complexity:

The space complexity is determined by the amount of stack space used by the recursive calls. In the worst case, the recursion goes as deep as the maximum depth of the multilevel linked list, which is O(n) if every node has a child and no next. However, in the best case, where the list is already a flat doubly linked list with no child pointers, the space complexity is O(1) since the recursive function preorder() is not called.

The average case would depend on the structure of the multilevel doubly linked list but is typically less than O(n) since not all nodes will have a child. Regardless, the worst-case space complexity can be stated as O(n) since this represents the maximum space that could be required in the presence of a deep nesting structure of child nodes.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫