algoadvance

Leetcode 430. Flatten a Multilevel Doubly Linked List

Problem Statement

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, as shown in the example below.

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:

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

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

Clarifying Questions

  1. Is the input always valid? Yes, you can assume the input will always be a valid multilevel doubly linked list.

  2. Are there any constraints on the values of the nodes? No, the problem is focused on the structure, not the values.

  3. Is there a maximum depth for the children? No, there is no specified limit to the depth, but the problem assumes it fits within the memory limits.

Strategy

  1. Traversal with a Stack: A suitable method for this problem is to use a depth-first search approach facilitated by a stack. This way, we can keep track of nodes to visit next while processing the current node.

  2. Modify Pointers: Traverse the list, and whenever a child is encountered, push the current node’s next node to the stack and then process the child node. Continue this until the whole structure is flattened.

  3. Edge Cases:

    • Empty list (null head)
    • Single node without children
    • Nodes with children but no next node

Code

// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

        Node pseudoHead = new Node();
        pseudoHead.next = head;
        Node curr, prev = pseudoHead;

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(head);

        while (!stack.isEmpty()) {
            curr = stack.pop();
            prev.next = curr;
            curr.prev = prev;

            if (curr.next != null) {
                stack.push(curr.next);
            }
            if (curr.child != null) {
                stack.push(curr.child);
                curr.child = null; // Don't forget to remove all child pointers.
            }

            prev = curr;
        }

        // detach the pseudo head from the real head
        pseudoHead.next.prev = null;
        return pseudoHead.next;
    }
}

Explanation

  1. Pseudo Head Node: A pseudo head node is used to simplify handling the prev pointers. It creates a dummy starting point that helps manage the head of the list easily.

  2. Stack Operations: Using a stack, we traverse the list depth-first. Whenever a child node is found, its next node is pushed onto the stack and the child node is processed.

  3. Pointer Adjustments: For each node processed, the next and prev pointers are adjusted to include the node in the flat list. The child pointer is nullified after it is processed to maintain proper list structure.

  4. Returning the Result: The pseudo head is detached from the resulting list to yield the correct structure starting from the original head node.

Time Complexity

This solution ensures that all nodes, including those in any nested children, are properly flattened into a single, doubly linked list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI