Flatten a Multilevel Doubly Linked List

Problem Statement

In this problem, you are provided with a unique data structure - a doubly linked list extended with a child pointer that may point to another doubly linked list. These chained lists can create deep hierarchies or multilevel structures. Your task is to flatten this multilevel doubly linked list so that all nodes are in a single, linear doubly linked list. Specifically, if a node named curr has a child list, the entire child list should be unpacked and inserted between curr and curr.next. In the end, you should return the head of the flattened list, all child pointers set to null indicate that the list has been correctly flattened.

Examples

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

Approach and Intuition

The key to solving the flattening of a multilevel doubly linked list lies in correctly and systematically processing the child pointers and integrating those child lists into the main list.

1. Tracking Nodes: Start from the head of the list and iterate through each node. For each node encountered, check if there is a child node associated with it.

2. Processing Child Nodes:

   • If a child is found, detach this sublist from the main list by setting the child pointer to null for the current node.
   • Integrate this child list into the main list. The integration is done at the place right after the current node and before the next node of the current node.

3. Managing Integration Seamlessly:

   • To do this integration, you would need to get to the end of the child list, connect the last node of this child list to curr.next, and also update the previous pointer of the curr.next (if it exists) to the last node of the child list.
   • Continue the iteration but now integrate the lists one node at a time, and each sublist similarly upon encountering a new child list recursively.

4. Ensuring Continuous Integration: As you continue through each node, make sure to check for further child lists even within newly integrated nodes since it can be a recursively defined structure.

By recursively and iteratively integrating child lists directly into the main list as soon as they are encountered, this approach ensures that all nodes are processed and the list is flattened sequentially. This method is robust because it deals dynamically with varying list depths and complex child-to-child connections without losing track of the main list's flow.

Solutions

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

    Node tempHead = new Node(0, null, head, null);
    Node current, previous = tempHead;

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

    while (!nodesStack.isEmpty()) {
      current = nodesStack.pop();
      previous.next = current;
      current.prev = previous;

      if (current.next != null) nodesStack.push(current.next);
      if (current.child != null) {
        nodesStack.push(current.child);
        current.child = null;
      }
      previous = current;
    }
    tempHead.next.prev = null;
    return tempHead.next;
  }
}