Flattening a Linked List Hard 0 attempts
GeeksforGeeks ↗

Flattening a Linked List

Hard Linked List GeeksforGeeks

You're given a linked list where each node sits at the head of its own sorted sub-list: alongside a next pointer connecting it to the following node in the main list, every node also has a bottom pointer leading down through its own vertical sorted list. Merge everything into one fully sorted list that's linked purely through bottom pointers.

Input Format
Implement flatteningALinkedList(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Each inner array is one sorted bottom chain. The editor builds nodes with data, bottom, and next properties.
Output Format
Return the result described in the statement. The output is read along bottom pointers as an array of node.data values.

Sample Input and Output

Example 1 · Run Sample

Input
root = [[5,7,8,30],[10,20],[19,22,50],[28,35,40,45]]
Output
[5,7,8,10,19,20,22,28,30,35,40,45,50]

Example 2

Input
root = [[1,2]]
Output
[1,2]
Constraints
  • 0 <= number of bottom lists <= 50
  • Each bottom list is sorted in non-decreasing order and non-empty.
  • 1 <= node.data <= 1000
Test Cases (2)
Case 1
Args: [[[5,7,8,30],[10,20],[19,22,50],[28,35,40,45]]] Expected: [5,7,8,10,19,20,22,28,30,35,40,45,50]
Case 2
Args: [[[1,2]]] Expected: [1,2]
Topics
Linked List

Approach: Merge the Bottom Lists

Walk the horizontal chain, saving each next pointer before merging its sorted bottom list into the accumulated result. Clear horizontal links so the output is a single bottom chain.

javascript
function flatteningALinkedList(root) {
  function merge(a, b) {
    const dummy = { bottom: null };
    let curr = dummy;
    while (a && b) {
      if (a.data <= b.data) { curr.bottom = a; a = a.bottom; }
      else { curr.bottom = b; b = b.bottom; }
      curr = curr.bottom;
    }
    curr.bottom = a || b;
    return dummy.bottom;
  }
  if (!root) return null;
  // Save each horizontal successor before merging; merged nodes use bottom only.
  let result = null, current = root;
  while (current) {
    const next = current.next;
    current.next = null;
    result = merge(result, current);
    current = next;
  }
  for (let node = result; node; node = node.bottom) node.next = null;
  return result;
}

Time Complexity: O(N × k) in the worst case, where N is the total number of nodes and k is the number of bottom lists

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript