Hard
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: []
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.lists[i].length
won’t exceed 10^4
.To solve the “Merge k Sorted Lists” problem in Swift with a Solution
class, we can use a priority queue (min-heap) to efficiently merge the lists. Here are the steps:
Solution
class.mergeKLists
that takes an array of linked lists lists
as input and returns a single sorted linked list.lists
and add the head node of each list to the priority queue.current
to point to the dummy node.next
pointer of the current
node to this node.current
pointer to the next node in the merged linked list.next
pointer, add the next node from the same list to the priority queue.next
pointer of the dummy node, which points to the head of the merged sorted linked list.Here’s the implementation:
class Solution {
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
var array: [Int] = []
let node = ListNode(0)
for list in lists {
var head: ListNode? = list
while head != nil {
array.append(head!.val)
head = head?.next
}
}
if !array.isEmpty {
array.sort()
var link = ListNode(array[0])
node.next = link
for i in array.dropFirst() {
link.next = ListNode(i)
if let next = link.next {
link = next
}
}
}
return node.next
}
}
This implementation provides a solution to the “Merge k Sorted Lists” problem in Swift using a priority queue.