链接

https://leetcode.com/problems/merge-k-sorted-lists/

难度

Hard

描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

给定K个有序链表，要求将它所有的元素归并到一个链表，并且有序。

样例:

Input:
[
   1->4->5,
  1->3->4,
  2->6
]
Output: 1- >1->2->3->4->4->5->6

题解

按照惯例，我们还是先来看最简单的解法，也就是暴力法。

暴力

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import sys

        ret = ListNode()
        pnt = ret

while True:
            mini = sys.maxsize
            node = None
# 遍历所有的链表
for i, l in enumerate(lists):
if l is None:
continue
if l.val < mini:
                    mini = l.val
                    node = i
# 如果node为None，说明所有的元素都已经归并结束了
if node is None:
break
            pnt.next = ListNode(mini)
            pnt = pnt.next
            lists[node] = lists[node].next
return ret.next

归并

class Solution:

def mergeTwoList(self, l1, l2):
        ret = ListNode()
        pnt = ret
while True:
"""
            链表没办法像数组那样在末尾插入标兵了
            所以只能人工判断是否为空的情况
            """
if l1 is None and l2 is None:
break
if l1 is None:
                pnt.next = ListNode(l2.val)
                pnt = pnt.next
                l2 = l2.next
elif l2 is None:
                pnt.next = ListNode(l1.val)
                pnt = pnt.next
                l1 = l1.next
else:
if l1.val < l2.val:
                    pnt.next = ListNode(l1.val)
                    l1 = l1.next
else:
                    pnt.next = ListNode(l2.val)
                    l2 = l2.next
                pnt = pnt.next
return ret.next

def dfs(self, lists, l, r):
"""
        递归合并K个链表
        这里的l和r维护的是闭区间
        """
if l > r:
return None
if l == r:
return lists[l]
else:
            mid = (l + r) // 2
return self.mergeTwoList(self.dfs(lists, l, mid), self.dfs(lists, mid+1, r))

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# 传入l=0， r=len(lists)-1，因为是闭区间
return self.dfs(lists, , len(lists)-1)

优先队列

class Solution:

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
class Node:
"""
            存储在优先队列当中的节点
            """
def __init__(self, val, arr):
                self.val = val
                self.arr = arr

# 重载判断大小的比较函数
def __lt__(self, other):
return self.val < other.val

import heapq
        arr = []
# 将所有链表插入优先队列当中
for l in lists:
if l is not None:
                heapq.heappush(arr, Node(l.val, l.next))

        ret = ListNode()
        pnt = ret

while len(arr) > :
# 从优先队列头部获取元素，需要注意，pop之后元素会从队列中删除
            node = heapq.heappop(arr)
            val, l = node.val, node.arr
            pnt.next = ListNode(val)
            pnt = pnt.next

# 获取完头部元素之后，将剩下的链表插入回队列当中
if l is not None:
                heapq.heappush(arr, Node(l.val, l.next))

return ret.next