【LeetCode】0023 合并k个排序链表

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