Merge K Sorted Lists

Difficulty: Hard

Problem

You are given an array of k linked lists, each sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

Example

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Merging all three sorted lists into one sorted list: 1→1→2→3→4→4→5→6.

Brute-force approach — Collect All Values, Sort, Rebuild

Collect all node values into an array, sort the array, then create a new linked list from the sorted values.

Steps

  1. Traverse all k lists, collect all values into one array
  2. Sort the array
  3. Build a new linked list from the sorted array
  4. Return the new list

Time complexity: O(N log N) · Space complexity: O(N)

Trade-offs

  • O(N log N) time is worse than O(N log k) when k << N
  • O(N) extra space for the values array

Optimal approach — Merge Pairs — Divide and Conquer

Key insight: Merge lists in pairs each round, halving the count. After log(k) rounds, one sorted list remains.

Pair up k lists and merge each pair using merge-two-sorted-lists. After each round, k lists become k/2. Repeat until one list remains. This is O(N log k) time.

Steps

  1. While more than one list remains:
  2. Pair up adjacent lists
  3. Merge each pair into one sorted list
  4. Replace lists with merged results
  5. Return the single remaining list

Time complexity: O(N log k) · Space complexity: O(1)