23. Merge k Sorted Lists

Loading...LeetCode

21. Merge Two Sorted Lists

算是 Q21 的进阶版，想要简单复制 Q21 的思路，依次比较当前k个候选，排最小的val进入结果。然后就TLE了...看来线性时间 O(k*N) 过不了。

这个思路下，每次都要比较k个候选，很多node被拿来比较了多次。要减少这个重复，可以把lists两两merge，直到merge成一个，其实还是merge sort的思路，这样的话可以直接copy Q21的code，加个iteration就可以了。

另一个优化思路是，既然这边每次都要对k个候选node比较出最小值，直接维护compare这个数组的最小值即可，改用heap来实现，过了。

Compare at Each Node (TLE)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        res = ListNode(0)
        cur = res
        while True:
            compare = {}
            for n, l in enumerate(lists):
                if l: compare[n] = l.val
            if not compare: break
            pick = min(compare.items(), key = lambda item :item[1])
            cur.next = lists[pick[0]]
            cur = cur.next
            if lists[pick[0]]: lists[pick[0]] = lists[pick[0]].next

        return res.next

Merge Sort

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
            res = ListNode(val=0)
            cur = res
            while l1 and l2:
                if l1.val < l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            cur.next = l1 if l1 else l2
            return res.next
        
        n, skip = len(lists), 1
        while skip < n:
            for i in range(0, n-skip, skip*2):
                lists[i] = mergeTwoLists(lists[i], lists[i - skip])
            skip *= 2
        return lists[0]

Heap

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        prQ = []
        for idx, node in enumerate(lists):
            if node:
                heapq.heappush(prQ, (node.val, idx))
        
        preHead = ListNode(0)
        curr = preHead
        while prQ:
            v, idx = heapq.heappop(prQ)
            curr.next = ListNode(v)
            curr = curr.next
            lists[idx] = lists[idx].next
            if lists[idx]:
                heapq.heappush(prQ, (lists[idx].val, idx))
        
        return preHead.next