Flatten a multilevel Doubly Linked List

XXX. Flatten a Multilevel Doubly Linked List

Linked List

Recursion

Problem Statement:

You are given a doubly linked list with one additional pointer child, 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. Flatten the list so that all the nodes appear in a single-level doubly linked list. The flattened list should use the next and prev pointers.

Algorithm:

1. Start traversing the list from the head node.
2. When encountering a node with a child pointer:
• Store the current node's next pointer in a temporary variable right.
• Recursively flatten the child list and link it to the current node's next.
• Update the flattened child list's prev pointer to point back to the current node.
• Traverse to the end of the flattened child list.
• Reconnect the previously stored right node to the end of the flattened child list, if it exists.
3. Continue traversing the list until the end is reached.

Complexity:

Time Complexity: O(n), where n is the total number of nodes in the list. Each node is processed once.
Space Complexity: O(d), where d is the maximum depth of the multilevel linked list due to recursive calls.

Java Implementation:

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}

public class Solution {
    public Node flatten(Node head) {
        Node p = head; 
        // Traverse the list
        while (p != null) {
            if (p.child != null) {
                // Store the current node's next pointer
                Node right = p.next; 
                
                // Process the child list recursively
                p.next = flatten(p.child);
                p.next.prev = p;
                p.child = null; 
                
                // Traverse to the end of the flattened child list
                while (p.next != null)
                    p = p.next;
                
                // Reconnect the original next pointer
                if (right != null) { 
                    p.next = right;
                    p.next.prev = p; 
                }
            }
            // Move to the next node
            p = p.next;
        }
        return head; 
    }
}