HardLinked ListsAI interview only
Merge K Sorted Lists
Asked atamazongooglemetamicrosoftuberbloombergapple
01 · Problem
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.
02 · Examples
Example 01
Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]
All three sorted linked lists are merged into a single sorted linked list by repeatedly picking the smallest available node.
Example 02
Input
lists = []
Output
[]
The input is an empty array of lists, so the result is an empty list.
Example 03
Input
lists = [[]]
Output
[]
The input contains one empty linked list, so the result is an empty list.
03 · Constraints
- 01k == lists.length
- 020 <= k <= 104
- 030 <= lists[i].length <= 500
- 04-104 <= lists[i][j] <= 104
- 05lists[i] is sorted in ascending order.
- 06The sum of lists[i].length will not exceed 104.
04 · Optimal complexity
- Time
- O(N log k)
- Space
- O(k)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.