Merge K Sorted Lists
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: []
Examples
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: All three sorted linked lists are merged into a single sorted linked list by repeatedly picking the smallest available node.
Example 2
Input: lists = []
Output: []
Explanation: The input is an empty array of lists, so the result is an empty list.
Example 3
Input: lists = [[]]
Output: []
Explanation: The input contains one empty linked list, so the result is an empty list.
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.
Optimal Complexity
Time
O(N log k)
Space
O(k)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview