Skip to main content
Back to ChallengesMerge K Sorted Linked ListsHard 50 min

Merge K Sorted Linked 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.

*Note: Since the execution environment uses flat inputs, we will pass arrays representing the linked lists, and you should return an array representing the merged list.*

Examples

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
The linked-lists are: 1->4->5, 1->3->4, 2->6. Merged into: 1->1->2->3->4->4->5->6.

Constraints

  • • k == lists.length
  • • 0 <= k <= 10^4
  • • 0 <= lists[i].length <= 500

Complexity Analysis

Time
O(N log N) using standard sort, or O(N log K) using PQ/Merge.
Space
O(N) to store flattened elements.

Test Cases

#1 Standard lists
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Expected: [1,1,2,3,4,4,5,6]
#2 Empty lists
Input: lists = []
Expected: []
JavaScript
Output
Click "Run Code" to see output here...