Merge k Sorted Lists

hard, linked list

Question

将k个有序链列合并为一个有序链列，注意分析算法复杂度

Solution

最直观最粗暴的方法是一个一个的比较，就可以使用Merge Two sorted list 合并有序数列来解决问题。假设每个链列有n个节点，第一次融合最糟糕需要比较2n次，第二次最糟糕需要2n+n次，。。。,总的需要2n+3n+...+kn=O(kn**2)

使用堆栈，将各个list的最小的数放入堆栈筛选，每个数的cost是log(k),一个nk个数，所以time complexity是nklog(k), 因为额外的堆栈，space complexity是O(k)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        from heapq import heappush, heappop, heapreplace, heapify
        dummy =  ListNode(0)
        node = dummy
        h = [(n.val, n) for n in lists if n]
        heapify(h)
        while h:
            v, n = h[0]
            if n.next is None:
                heappop(h) #only change heap size when necessary
            else:
                heapreplace(h, (n.next.val, n.next))
            node.next = n
            node = node.next
            
        return dummy.next

另外一个方法借助Queue() package

from Queue import PriorityQueue
class Solution(object):
    def mergeKLists(self, lists):
        dummy = ListNode(None)
        curr = dummy
        q = PriorityQueue()
        for node in lists:
            if node: q.put((node.val,node))
        while q.qsize()>0:
            curr.next = q.get()[1]
            curr=curr.next
            if curr.next: q.put((curr.next.val, curr.next))
        return dummy.next

也可以借助Merge Two sorted list 合并有序数列但是使用divide and conquer的办法

def mergeKLists(self, lists):
    if not lists:
        return None

    while len(lists) > 1:
        merged = []
        while len(lists) > 1:
            merged.append(self.merge(lists.pop(), lists.pop()))
        lists += merged
    return lists[0]
    
def merge(self, x, y, s):
    dummyHead = ListNode(0)
    p = dummyHead
    while x and y:
        if x.val < y.val:
            p.next = x
            x = x.next
        else:
            p.next = y
            y = y.next
        p = p.next
    p.next = x if x else y
    return dummyHead.next