Q23: Merge K Sorted Lists

Merge $k$ sorted linked lists into one consolidated sorted list using Divide and Conquer or Min-Heap.

Divide and Conquer List Merger

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  
  while (lists.length > 1) {
    const mergedLists = [];
    for (let i = 0; i < lists.length; i += 2) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null;
      mergedLists.push(mergeTwoLists(l1, l2));
    }
    lists = mergedLists;
  }
  return lists[0];
}

function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}

💡 Pairs up lists and merges each pair using mergeTwoLists, halving the total number of lists each pass until only one sorted list remains.

Key Takeaways

Divide and conquer merges pairs of lists iteratively.
Reduces time complexity to O(N log k) where N is total node count across k lists.

Knowledge Check

What is the time complexity of merging K sorted lists with total N nodes using Divide and Conquer?

Q23: Merge K Sorted Lists

STAY UPDATED WITH BYTES!