23-合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。

---

示例

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

---

解法

暴力法

核心思想：将所有结点的数据域val加入列表中，在对其排序，生成结点加入新链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        new_List = ListNode(None)
        p = new_List
        nodes = []
        # 将每个结点的值都加入列表中
        for l in lists:
            while l != None:
                nodes.append(l.val)
                l = l.next
        # 对列表进行排序，依次生成结点加入新链表
        for node in sorted(nodes):
            p.next=ListNode(node)
            p=p.next
        return new_List.next

优先级队列

核心思想：利用以数据域为优先级的队列，将每个未访问过得最前面的结点加入队列。这样出队的一定是当前数据域最小的结点，将其加入新链表中，并该节点的后继结点加入队列（如果存在的话）。

# 解法2:利用优先级队列
from Queue import PriorityQueue

class Solution2:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = point = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                # 根据结点的数据域val为优先级加入队列
                q.put((l.val, l))
        # 每次取出最小的数据域的结点，
        # 再将取出的结点后继加入队列。
        while not q.empty():
            val, node = q.get()
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

---

来源

LeetCode中该题地址，Click here!