Question
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
Solution
Use a min heap to store the head of the lists. \(O(nlogk)\) time complexity and \(O(k)\) space complexity.
import scala.collection.mutable.PriorityQueue
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
object Solution {
def mergeKLists(lists: Array[ListNode]): ListNode = {
if(lists.size == 0)
return null
implicit object ListNodeOrdering extends Ordering[ListNode] {
override def compare(n1: ListNode, n2: ListNode): Int = {
-(n1.x compare n2.x)
}
}
val queue = new PriorityQueue[ListNode]()
lists.foreach { l =>
if(l != null)
queue.enqueue(l)
}
if(queue.headOption.isEmpty)
return null
val head = queue.dequeue()
var prev = head
if(head.next != null) {
queue.enqueue(head.next)
}
while(queue.headOption.isDefined) {
val node = queue.dequeue()
prev.next = node
prev = node
if(node.next != null) {
queue.enqueue(node.next)
}
}
head
}
}