H-23. Merge k Sorted Lists

Loading...LeetCode

# 自己的解法...貌似和暴力解一样, O(Nlog(N))
# 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:
        all_nodes = []
        for ln in lists:
            cur = ln
            while cur:
                heapq.heappush(all_nodes, cur.val)
                cur = cur.next
        
        res_ln = ListNode(-1)
        cur = res_ln
        for i in range(len(all_nodes)):
            cur.next = ListNode(heapq.heappop(all_nodes))
            cur = cur.next
        return res_ln.next
        
# 另一个思路, 不要把所有node一次性放到heap, 而是放入(val, ListNode)对, 这样heap的大小
# 只用维持在k(即链表数量), 做一次pop和push的复杂度也只有logK. 而一共进行k次push, N次pop,
# 所以复杂度是NlogK.(注意k肯定是小于等于N的..)
 
# 一个错误解法:
# 会报TypeError '<' not supported between instances of 'ListNode' and 'ListNode'的错误
# 因为heappush的时候, 先比较tuple的第0位, 如果相同, 会比较第1位, 但是这题里面, listNode没有
# 实现__lt__函数, 所以没法比较, 然后就报错了.
import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        list_heap = []
        for ln in lists:
            heapq.heappush(list_heap, (ln.val, ln))
        
        res = cur = ListNode(-1)
        
        while list_heap:
            target_tuple = heapq.heappop(list_heap)
            cur.next = ListNode(target_tuple[0])
            cur = cur.next
            rest_ln = target_tuple[1].next
            if rest_ln:
                heapq.heappush((rest_ln.val, rest_ln))
        
        return res.next

# 针对上面错误解法, 有两个解决方案:
# 1. 写一个Wrapper类, 实现其__lt__方法.
# 2. tuple第1位变成id(ln)(输出ln的内存地址, 这个值是独一无二的)

# 方法1:
import heapq
class Wrapper:
    def __init__(self, ln):
        self.ln = ln
    def __lt__(self, other):
        return self.ln.val < other.ln.val

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        list_heap = []
        for ln in lists:
            if ln:
                heapq.heappush(list_heap, Wrapper(ln))
        
        res = cur = ListNode(-1)
        
        while list_heap:
            wrapper = heapq.heappop(list_heap)
            cur.next = wrapper.ln
            cur = cur.next
            rest_ln = wrapper.ln.next
            if rest_ln:
                heapq.heappush(list_heap, Wrapper(rest_ln))
        
        return res.next
        
# 方法2:
import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        list_heap = []
        for ln in lists:
            if ln:
                heapq.heappush(list_heap, (ln.val, id(ln), ln))
        
        res = cur = ListNode(-1)
        
        while list_heap:
            target_tuple = heapq.heappop(list_heap)
            cur.next = ListNode(target_tuple[0])
            cur = cur.next
            rest_ln = target_tuple[2].next
            if rest_ln:
                heapq.heappush(list_heap, (rest_ln.val, id(rest_ln), rest_ln))
        
        return res.next