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 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注