Merge K-Sorted Lists

This is a Hard-level Leetcode problem although the solution looks very trivial to me.

import java.util.*

class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        var queue = PriorityQueue<Int>()
        lists.forEach { 
            var node: ListNode? = it
            while(node != null){
                queue.add(node?.`val`)
                node = node.next
            }
        }
        
        val top = ListNode(-1)
        var output = top
        while(!queue.isEmpty()){
            val value = queue.poll()            
            output.next = ListNode(value)
            output = output.next
        }
        
        return top.next
    }
}

The code loops through the arrays of linked list and insert each value to a priority queue. The priority queue sorts the values during insertion so we don’t have to do a separate sort(). Next, traverse the queue and generate the linked list as our function output.

The Java implementation of (PriorityQueue)[https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html] uses priority heap and queueing and dequeuing takes O(logn). Even though that is the case, the peformance is still quite ok compared to other submitted solutions in Leetcode.

Runtime: 184 ms, faster than 97.37% of Kotlin online submissions for Merge k Sorted Lists.
Memory Usage: 36.5 MB, less than 100.00% of Kotlin online submissions for Merge k Sorted Lists.

Marc Lester Tan