Merge k Sorted Lists Hard 0 attempts
LeetCode ↗

Merge k Sorted Lists

Hard Linked List LeetCode

You are given an array of k linked lists lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it. Lists are represented as arrays of sorted values.

Example 1:

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

Example 2:

Input: lists = []
Output: []
Sample Input
—
Sample Output
—
Constraints
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
Test Cases
Case 1
Args: [[[1,4,5],[1,3,4],[2,6]]] Expected: [1,1,2,3,4,4,5,6]
Case 2
Args: [[]] Expected: []
Topics
Linked List

Divide and Conquer

function mergeKLists(lists) {
  if (!lists.length) return null;
  function merge(a, b) {
    const dummy = {next: null}; let curr = dummy;
    while (a && b) {
      if (a.val <= b.val) { curr.next = a; a = a.next; }
      else { curr.next = b; b = b.next; }
      curr = curr.next;
    }
    curr.next = a || b;
    return dummy.next;
  }
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2)
      merged.push(i+1 < lists.length ? merge(lists[i], lists[i+1]) : lists[i]);
    lists = merged;
  }
  return lists[0];
}

Time: O(N log k) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript