Code Implementation

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def flatten_rec(node):
            curr = node
            last = node
            while curr:
                nxt = curr.next
                if curr.child:
                    child_head = curr.child
                    child_tail = flatten_rec(child_head)
                    curr.next = child_head
                    child_head.prev = curr
                    if nxt:
                        child_tail.next = nxt
                        nxt.prev = child_tail
                    curr.child = None
                    last = child_tail
                else:
                    last = curr
                curr = nxt
            return last
        flatten_rec(head)
        return head
      

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/
class Solution {
public:
    Node* flatten(Node* head) {
        flattenDFS(head);
        return head;
    }
    
    Node* flattenDFS(Node* node) {
        Node* curr = node;
        Node* last = node;
        while (curr) {
            Node* nxt = curr->next;
            if (curr->child) {
                Node* child_head = curr->child;
                Node* child_tail = flattenDFS(child_head);
                curr->next = child_head;
                child_head->prev = curr;
                if (nxt) {
                    child_tail->next = nxt;
                    nxt->prev = child_tail;
                }
                curr->child = nullptr;
                last = child_tail;
            } else {
                last = curr;
            }
            curr = nxt;
        }
        return last;
    }
};
      

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/
class Solution {
    public Node flatten(Node head) {
        flattenDFS(head);
        return head;
    }
    
    private Node flattenDFS(Node node) {
        Node curr = node;
        Node last = node;
        while (curr != null) {
            Node nxt = curr.next;
            if (curr.child != null) {
                Node childHead = curr.child;
                Node childTail = flattenDFS(childHead);
                curr.next = childHead;
                childHead.prev = curr;
                if (nxt != null) {
                    childTail.next = nxt;
                    nxt.prev = childTail;
                }
                curr.child = null;
                last = childTail;
            } else {
                last = curr;
            }
            curr = nxt;
        }
        return last;
    }
}
      

/**
 * // Definition for a Node.
 * function Node(val, prev, next, child) {
 *     this.val = val;
 *     this.prev = prev;
 *     this.next = next;
 *     this.child = child;
 * };
 */
/**
 * @param {Node} head
 * @return {Node}
 */
var flatten = function(head) {
    function flattenDFS(node) {
        let curr = node;
        let last = node;
        while (curr) {
            let nxt = curr.next;
            if (curr.child) {
                let childHead = curr.child;
                let childTail = flattenDFS(childHead);
                curr.next = childHead;
                childHead.prev = curr;
                if (nxt) {
                    childTail.next = nxt;
                    nxt.prev = childTail;
                }
                curr.child = null;
                last = childTail;
            } else {
                last = curr;
            }
            curr = nxt;
        }
        return last;
    }
    flattenDFS(head);
    return head;
};
      

Problem Description

You are given the head of a multilevel doubly linked list. Each node in this list contains:

• An integer value val
• Pointers prev and next to the previous and next nodes, respectively
• An optional child pointer that may point to another doubly linked list (the child list)

Your task is to flatten the list so that all nodes appear in a single-level, doubly linked list. The nodes should appear in a depth-first order: for each node, after itself, its child list (if any) should be inserted before its next node. All child pointers must be set to null in the flattened list.

Constraints:

• There is only one valid way to flatten the list.
• Do not create new nodes; reuse the existing nodes and adjust their pointers.
• Do not use extra data structures to store the nodes.

Thought Process

When approaching this problem, the first idea that might come to mind is to traverse the list and, whenever a node has a child, insert the entire child list between the current node and its next node. This requires careful pointer manipulation to preserve the doubly linked nature and not lose track of the rest of the list.

A brute-force approach could be to collect all the nodes in a flat array, then reconstruct the list. However, this would violate the constraints of not using extra data structures and not creating new nodes.

Therefore, we need an in-place algorithm. The recursive nature of the multilevel structure suggests that a depth-first traversal would be effective. At each node, we process its child (if present) before moving to the next node. This way, we can "splice" the child list into the main list at the correct position.

The challenge is to keep track of the tail of the flattened child list so we can reconnect the next node properly. We also need to ensure that all child pointers are set to null after flattening.

Solution Approach

The solution uses a recursive depth-first traversal to flatten the multilevel doubly linked list in place. Here’s a step-by-step breakdown:

1. Start at the head node. For each node, check if it has a child.
2. If the node has a child:
   • Recursively flatten the child list. This returns the tail node of the flattened child list.
   • Connect the current node’s next pointer to the child, and set the child’s prev to the current node.
   • If the current node had a next node, connect the tail of the child list to it, and set the next node’s prev to the child list’s tail.
   • Set the current node’s child pointer to null.
   • Continue from the tail of the child list (since the next pointer now points to the child list).
3. If the node does not have a child: Move to the next node.
4. Return the last node processed (the tail). This is required for connecting the tail of a child list to the parent’s next node.
5. Repeat recursively. The recursion ensures all levels are flattened in a depth-first manner.

This method ensures all nodes are visited exactly once, and all pointers are updated in place, without extra data structures.

Example Walkthrough

Consider the following multilevel list:

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

Step-by-step:

1. Start at node 1, move to 2, then 3. Node 3 has a child (7).
2. Flatten the child list starting at 7:
   • 7 → 8 (8 has child 11)
   • Flatten 11 → 12 (no child): becomes 11-12
   • 8 connects to 11, 11 connects to 12, 12 connects to 9
   • Continue: 9 → 10 (no child)
   • Child list flattened: 7-8-11-12-9-10
3. Insert flattened child list after 3, before 4. The sequence is now: 1-2-3-7-8-11-12-9-10-4-5-6
4. Continue flattening the rest (no more children): the list is fully flattened.

The final flattened list is: 1-2-3-7-8-11-12-9-10-4-5-6

Time and Space Complexity

Brute-force approach:

• If you collected all nodes in a list or array and then rebuilt the list, time would be O(N) but space would also be O(N) due to the extra data structure.

• Time Complexity: O(N), where N is the total number of nodes. Each node is visited exactly once.
• Space Complexity: O(D), where D is the maximum depth of the multilevel structure, due to recursion stack. In the worst case (a chain of child pointers), this could be O(N), but for most cases, it is much less.

No additional data structures are used beyond the recursion stack.

Summary

The problem of flattening a multilevel doubly linked list is elegantly solved using a recursive, depth-first traversal. The key insight is to process each child list in place, splicing it into the main list and updating all pointers as you go. This method respects all constraints: it does not use extra space (apart from the call stack), does not create new nodes, and guarantees the unique, correct order for the flattened list. The approach is efficient, easy to reason about, and leverages the recursive structure of the input data.