Flatten a Multilevel Doubly Linked List Medium 0 attempts
LeetCode ↗

Flatten a Multilevel Doubly Linked List

Medium Linked List LeetCode

You are given a doubly linked list where each node may have a child pointer to a separate doubly linked list. These child lists may also have children, forming a multilevel structure. Flatten the list so that all nodes appear in a single-level doubly linked list. Child lists should be inserted between the current node and its next node, depth-first. After flattening, no node should have a child pointer.

Example:

Input: [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]
Sample Input
—
Sample Output
—
Constraints
  • 0 <= number of nodes <= 1000
  • 1 <= Node.val <= 10^5
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.

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