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){
                node =
        val top = ListNode(-1)
        var output = top
            val value = queue.poll()            
   = ListNode(value)
            output =

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)[] 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.
comments powered by Disqus