loading

23. Merge k Sorted Lists — Step-by-Step Visualization

hardLeetCode #23Linked ListDivide and ConquerHeap

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]` **Example 2:** Input: `lists = []` Output: `[]` **Example 3:** Input: `lists = [[]]` Output: `[]`

Algorithm Pattern

Divide and Conquer

Key Idea

Take pairs of linked lists and merge them two at a time using a standard merge algorithm. Repeat this process until only 1 list remains.

Step-by-Step Approach

  1. Check if the `lists` array is empty or None.
  2. While `lists` has more than 1 linked list:
  3. Create an empty `mergedLists` buffer.
  4. Iterate through the `lists` array in steps of 2 (`i` and `i + 1`).
  5. Merge `lists[i]` and `lists[i + 1]`. If `i + 1` is out of bounds, just append `lists[i]`.
  6. Append the newly merged list to `mergedLists`.
  7. Over-write `lists = mergedLists` and repeat the loop until `len(lists) == 1`.
  8. Return `lists[0]`.

Common Gotchas

  • Instead of a Priority Queue (Min-Heap) which requires O(k) extra memory, this Divide and Conquer approach merges in-place maintaining strictly O(1) auxiliary memory space, returning identically stable O(N log k) time complexity.
  • Handling odd numbers of lists cleanly by simply letting the unmatched trailing list fall-through to the buffer unharmed.

Related Problems

← All problems