Merge K Sorted Lists

You are given an array of k sorted linked lists. Your task is to merge all of them into one single sorted linked list, and return its head.

Merge K Sorted Lists

Problem Statement

You are given an array of k sorted linked lists. Your task is to merge all of them into one single sorted linked list, and return its head.

Constraints

• k = lists.length
• 0 ≤ k ≤ 10³
• 0 ≤ lists[i].length ≤ 500
• −10³ ≤ lists[i][j] ≤ 10³
• Each lists[i] is already sorted in ascending order.
• The total number of elements across all lists will not go over 10³.

Examples

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

Explanation: Merging all the lists in sorted order gives [1, 1, 2, 3, 4, 4, 5, 6].

Output: [1, 1, 2, 3, 4, 4, 5, 6]

Example 2

Input: lists = []

Explanation: There are no lists to merge, so the result is an empty list.

Output: []

Example 3

Input: lists = [[]]

Explanation: The single list given is empty, so the merged result is also empty.

Output: []

Solution

We break this problem into two parts:

1. A helper function that merges two sorted linked lists into one.
2. A main function that uses this helper to merge all k lists together, one pair at a time.

Step 1: Merging Two Lists

• We create a dummy node to make building the new list easier.
• We use a pointer, curr, to keep track of where we're building the merged list.
• We compare the current nodes from both lists. Whichever one has the smaller value, we attach it next in our merged list, and move forward in that list.
• We keep doing this until one of the two lists runs out.
• Once one list is empty, we attach whatever is left of the other list directly to the end, since it's already sorted.

Step 2: Merging All K Lists

• We repeat a process of merging lists in pairs, over and over, until only one list remains.
• In each round:
  • We go through the lists two at a time.
  • We merge each pair using our helper function from Step 1.
  • If there's an odd one out (a list with no pair in this round), we just carry it forward unchanged to the next round.
• After each round, the number of lists roughly cuts in half. We repeat this until only one merged list is left, which is our final answer.

Code

function merge2Lists(head1, head2) {
  let dummy = new LinkedNode(0);
  let curr = dummy;

  while (head1 !== null && head2 !== null) {
    if (head1.data <= head2.data) {
      curr.next = head1;
      head1 = head1.next;
    } else {
      curr.next = head2;
      head2 = head2.next;
    }
    curr = curr.next;
  }

  curr.next = head1 !== null ? head1 : head2;
  return dummy.next;
}

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;

  // Keep merging pairs until one list remains
  while (lists.length > 1) {
    let merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      if (i + 1 < lists.length) {
        merged.push(merge2Lists(lists[i], lists[i + 1]));
      } else {
        merged.push(lists[i]);
      }
    }
    lists = merged;
  }

  return lists[0];  // Return the final merged list
}