Merge k Sorted Lists Hard 0 attempts
LeetCode ↗

Merge k Sorted Lists

Hard Linked List LeetCode

You're given an array lists holding k linked lists, each already sorted in ascending order. Combine all of them into one single sorted linked list and return it. Each list is represented here as an array of its sorted values.

Input Format
Implement mergeKLists(lists). Inputs below show JavaScript function arguments; there is no stdin parsing. Each inner array represents a linked list; the editor passes an array of list heads.
Output Format
Return the result described in the statement. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
lists = []
Output
[]
Constraints
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • At most 10^4 total nodes; each list is sorted.
  • -10^4 <= node.val <= 10^4
Test Cases (2)
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

javascript
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(k) for arrays of list heads (excluding output nodes)

Saved in this browser only. Private to you.

JavaScript