LeetCode: Merge k Sorted Lists

Posted on January 17, 2018July 26, 2020 by braindenny

Merge k Sorted Lists

Similar Problems:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Leave me comments, if you have better ways to solve.

Solution: heap

## https://code.dennyzhang.com/merge-k-sorted-lists
## Basic Ideas: heap
##
## Complexity: Time O(n*log(k)), Space O(1)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        l = []
        # minheap
        for i in range(len(lists)):
            node = lists[i]
            if node:
                heapq.heappush(l, (node.val, id(node), node))

        dummyHead = ListNode(0)
        p = dummyHead
        # heapq.heapify(l)
        while len(l)>0:
            (_, _, q) = heapq.heappop(l)
            if q.next:
                heapq.heappush(l, (q.next.val, id(q.next), q.next))
            p.next = q
            p = p.next

        # close the linked list
        p.next = None
        return dummyHead.next

Solution: heap

// https://code.dennyzhang.com/merge-k-sorted-lists
// Basic Ideas: heap
//    Maintain minheap
//    The top of the heap is the current element.
//    Pop the top.
//     If the element still has next node, push the next
//     Otherwise this list has been fully processed
// Complexity: Time O(n*log(K)), Space O(K)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
import "container/heap"

type MyHeap []*ListNode

func (h MyHeap) Len() int {
    return len(h)
}

func (h MyHeap) Less(i, j int) bool {
    return h[i].Val<h[j].Val
}

func (h MyHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MyHeap)Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}

func (h *MyHeap)Pop() interface{} {
    res := (*h)[len(*h)-1]
    *h = (*h)[0:len(*h)-1]
    return res
}

func mergeKLists(lists []*ListNode) *ListNode {
    res := &ListNode{} // dummy Node
    p := res

    h := &MyHeap{}
    heap.Init(h)
    for _, n := range lists {
        if n != nil {
            heap.Push(h, n)
        }
    }
    for h.Len()>0 {
        top := heap.Pop(h).(*ListNode)
        p.Next = top
        p = p.Next
        if top.Next != nil {
            heap.Push(h, top.Next)
        }
    }
    return res.Next
}

Post Views: 2