leetcodeday23 —合并K个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

思路:参考合并两个有序链表方法:

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        prehead = ListNode(-1)
        n=len(lists)
        x=[[10**4+1]*n]
        prev = prehead
        while lists!= [[None]*n]:
            list1=[]
            for i in  range(n):
                if lists[i]:
                    list1.append(lists[i].val)
                else:
                    list1.append(10**4+1)
            
            if list1==x[0]:
                break
            index=list1.index(min(list1))  
            prev.next = lists[index]
            
            lists[index]= lists[index].next  
           
            prev = prev.next
        return prehead.next

对于该例子超时了

看下leetcode给出的一些方法:

两两合并:

最简单方法:采用分治法,利用之前的两两合并的链表,逐个将K个链表合并。但这样效率较低,时间上只比16%的提交优秀。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        res = None #设置初始结果为空
        for listi in lists: #逐个遍历 两两合并
            res = self.mergeTwoLists(res, listi)
        return res
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0) #构造虚节点
        move = dummy #设置移动节点等于虚节点
        while l1 and l2: #都不空时
            if l1.val < l2.val:
                move.next = l1 #移动节点指向数小的链表
                l1 = l1.next
            else:
                move.next = l2
                l2 = l2.next
            move = move.next
        move.next = l1 if l1 else l2 #连接后续非空链表
        return dummy.next #虚节点仍在开头
  • 归并 :

最后的两链表合并部分不变,上部的两两合并改成归并形式的递归操作

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        n = len(lists) #记录子链表数量
        return self.mergeSort(lists, 0, n - 1) #调用归并排序函数
    def mergeSort(self, lists: List[ListNode], l: int, r: int) -> ListNode:
        if l == r:
            return lists[l]
        m = (l + r) // 2
        L = self.mergeSort(lists, l, m) #循环的递归部分
        R = self.mergeSort(lists, m + 1, r)
        return self.mergeTwoLists(L, R) #调用两链表合并函数
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0) #构造虚节点
        move = dummy #设置移动节点等于虚节点
        while l1 and l2: #都不空时
            if l1.val < l2.val:
                move.next = l1 #移动节点指向数小的链表
                l1 = l1.next
            else:
                move.next = l2
                l2 = l2.next
            move = move.next
        move.next = l1 if l1 else l2 #连接后续非空链表
        return dummy.next #虚节点仍在开头

最小堆:

思路:对所有的list中元素入堆,然后依次出堆到新的listnode中。

利用堆的数据结构,可以极大地简化代码。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq #调用堆
        minHeap = []
        for listi in lists: 
            while listi:
                heapq.heappush(minHeap, listi.val) #把listi中的数据逐个加到堆中
                listi = listi.next
        dummy = ListNode(0) #构造虚节点
        p = dummy
        while minHeap:
            p.next = ListNode(heapq.heappop(minHeap)) #依次弹出最小堆的数据
            p = p.next
        return dummy.next 

发表评论

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