https://leetcode-cn.com/problems/merge-k-sorted-lists/
# -*- coding:utf-8 -*- # 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 """ res = ListNode(None) point = res while len(lists) > 0: min_val = None for each in lists: if each is None: # lists.remove(each) continue if min_val is None or each.val < min_val.val: min_val = each if min_val is None: return res.next point.next = min_val point = point.next for i in range(len(lists)): if lists[i] is not None and lists[i].val == min_val.val: print(min_val.val) lists[i] = lists[i].next break return res.next if __name__ == '__main__': n1 = ListNode(1) n2 = ListNode(4) n3 = ListNode(5) n4 = ListNode(1) n5 = ListNode(3) n6 = ListNode(4) n7 = ListNode(2) n8 = ListNode(6) n1.next = n2 n2.next = n3 n4.next = n5 n5.next = n6 n7.next = n8 lists = [n1, n4, n7] print(Solution().mergeKLists1(lists))
思路:这道题的思路就是首先对比k个链表的首位,找出最小的那一个然后加到结果链表中继续向下查找。
思考:观察评论我们可以发现还有一个比较简单的做法,就是优先队列,类似于生成树和最大(小)堆,每次插入维护数据结构特性,出的时候输出最小的,这种结构往往是lgn级别的复杂度,因此相比于一般算法确实快了不少。下面贴一个优先队列实现的版本。
def mergeKLists1(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
from queue import PriorityQueue
head = point = ListNode(0)
q = PriorityQueue()
for each in lists:
while each is not None:
q.put(each.val)
each = each.next
while not q.empty():
val = q.get()
point.next = ListNode(val)
point = point.next
return head.next
0 条评论