Merge K Sorted Lists

Medium~30 min

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.

Examples

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: []
Explanation: The input is an empty list, so the merged list is also empty.
Example 3
Input: lists = [[]]
Output: []
Explanation: The input contains one empty linked list, so the result is empty.

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
  • Expected time complexity: O(n log k)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run