Golang solution (32ms) - Using the 'heap' interface


  • 0
    func mergeKLists(lists []*ListNode) *ListNode {
        minHeap := &MinHeap{}
        var dummyHead ListNode
        prev := &dummyHead
        for i := 0; i < len(lists); i++ {
            if lists[i] != nil {
                heap.Push(minHeap, &element{lists[i], i})
                lists[i] = lists[i].Next
            }
        }
        for minHeap.Len() != 0 {
            elem := heap.Pop(minHeap).(*element)
            prev.Next = elem.node
            prev = prev.Next
            if lists[elem.index] != nil {
                heap.Push(minHeap, &element{lists[elem.index], elem.index})
                lists[elem.index] = lists[elem.index].Next
            }
        }
        return dummyHead.Next
    }
    
    type element struct {
        node *ListNode
        index int
    }
    
    type MinHeap []*element
    func (h MinHeap) Len() int { return len(h) }
    func (h MinHeap) Less(i, j int) bool { return h[i].node.Val < h[j].node.Val }
    func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
    func (h *MinHeap) Push(value interface{}) { *h = append(*h, value.(*element)) }
    func (h *MinHeap) Pop() interface{} {
        min := (*h)[len(*h) - 1]
        *h = (*h)[:len(*h) - 1]
        return min
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.