Flatten a Multilevel Doubly Linked List Medium 0 attempts
LeetCode ↗

Flatten a Multilevel Doubly Linked List

Medium Linked List LeetCode

You're given a doubly linked list in which any node may additionally hold a child pointer to the head of its own separate doubly linked list, and those child lists can themselves contain further nested children, forming a multilevel structure. Collapse the entire structure into one single-level doubly linked list, inserting each child list depth-first between its parent node and the parent's original next node. Once flattened, no node should retain a child pointer.

Input Format
Implement flattenAMultilevelDoublyLinkedList(head). Inputs below show JavaScript function arguments; there is no stdin parsing. A multilevel list uses numbers or {val, child:[...]} entries. The editor builds doubly linked nodes with val, prev, next, and child properties.
Output Format
Return the result described in the statement. Output is a value array; prev pointers must be correct and child pointers must be null.

Sample Input and Output

Example 1 ยท Run Sample

Input
head = [1,{"val":2,"child":[3,{"val":4,"child":[5]}]},6]
Output
[1,2,3,4,5,6]

Example 2

Input
head = []
Output
[]
Constraints
  • 0 <= number of nodes <= 1000
  • 1 <= Node.val <= 10^5
Test Cases (2)
Case 1
Args: [[1,{"val":2,"child":[3,{"val":4,"child":[5]}]},6]] Expected: [1,2,3,4,5,6]
Case 2
Args: [[]] Expected: []
Topics
Linked List

Approach: Iterative with Stack

Traverse the list. When a node has a child, push its next onto a stack, then splice the child list in as the new next. When reaching a node with no next and the stack is non-empty, pop and continue from there.

javascript
function flattenAMultilevelDoublyLinkedList(head) {
  if (!head) return null;
  let curr = head;
  const stack = [];
  while (curr) {
    if (curr.child) {
      if (curr.next) stack.push(curr.next);
      curr.next = curr.child;
      curr.next.prev = curr;
      curr.child = null;
    }
    if (!curr.next && stack.length) {
      const next = stack.pop();
      curr.next = next;
      next.prev = curr;
    }
    curr = curr.next;
  }
  return head;
}

Time Complexity: O(n)

Space Complexity: O(n) for the stack

Saved in this browser only. Private to you.

JavaScript