Flattening a Linked List Hard 0 attempts
GeeksforGeeks ↗

Flattening a Linked List

Hard Linked List GeeksforGeeks

Given a linked list where every node represents a linked list and contains two pointers: (i) a next pointer to the next node in the main list, (ii) a bottom pointer to a linked list where this node is the head. All the bottom linked lists are sorted. Flatten the list into a single sorted list using the bottom pointer.

Example:

Input: 5->10->19->28 with bottom lists 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
Sample Input
—
Sample Output
—
Constraints
  • 0 <= N <= 50
  • 1 <= Node.val <= 10^3
Topics
Linked List

Approach: Merge from Right to Left

Start from the rightmost two lists and merge them into a sorted list using the bottom pointer. Continue merging the result with the next list to the left until all lists are merged into one sorted bottom list.

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;
  let result = root;
  while (result.next) {
    result = merge(result, result.next);
  }
  return result;
}

Time Complexity: O(n*m) where n is number of main nodes and m is average bottom list length

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript