Merge k Sorted Lists — Hard Coding Interview Question

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]

Constraints

• k == lists.length
• 0 ≤ k ≤ 10⁴
• 0 ≤ lists[i].length ≤ 500
• -10⁴ ≤ lists[i][j] ≤ 10⁴

Topics & Companies

Topics: linked-list, heap, recursion

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(n log k). Space complexity: O(log k) recursion/iteration state.

Practice more

• All DSA Problems
• DSA Patterns