[LeetCode] 23. Merge k Sorted Lists

Table of Contents

Description

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.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:

[
  1 -> 4 -> 5,
  1 -> 3 -> 4,
  2 -> 6
]
merging them into one sorted list:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• $k == lists.length$
• $0 <= k <= 10^4$
• $0 <= lists[i].length <= 500$
• $-10^4 <= lists[i][j] <= 10^4$
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed $10^4$.

Approach

We can use the approach of merging two sorted linked lists to merge k sorted linked lists by dividing and conquering the lists into two halves and merging them recursively. Therefore, we can reduce the complexity of merging k lists from $O(n\cdot k)$ to $O(n\cdot \log k)$.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists, left = 0, right = lists.length - 1) {
  // If the list is empty, return null.
  if (lists.length === 0) return null;

  // If there is only one list in the current range, return it.
  if (left === right) return lists[left];

  // Find the middle index to divide the lists into two halves.
  const mid = Math.floor((left + right) / 2);

  // Recursively merge the left half.
  const list1 = mergeKLists(lists, left, mid);

  // Recursively merge the right half.
  const list2 = mergeKLists(lists, mid + 1, right);

  // Merge the two sorted halves.
  return mergeTwoLists(list1, list2);
};

var mergeTwoLists = function (list1, list2) {
  // If either list is null, return the other list.
  if (!list1 || !list2) return list1 || list2;

  // Compare the current nodes of both lists.
  if (list1.val < list2.val) {
    // If list1's value is smaller, recursively merge list1.next with list2.
    list1.next = mergeTwoLists(list1.next, list2);

    return list1;
  }
  // Otherwise, recursively merge list1 with list2.next.
  list2.next = mergeTwoLists(list1, list2.next);

  return list2;
};

Complexity Analysis

Time Complexity

The time complexity of this algorithm is $O(n\cdot \log k)$, where n is the total number of nodes in all linked lists and k is the number of linked lists. This is because we divide the problem into two halves at each step, and merging two sorted linked lists takes linear time.

Space Complexity

The space complexity is $O(\log k)$, which comes from the recursion stack depth when merging the lists using divide-and-conquer algorithm. Each merge operation for two lists uses $O(1)$ extra space, but the maximum recursion depth is $\log k$.