Leetcode23. 合并k个升序链表

一、题目描述：

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

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

1. 示例 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. 示例 2：
   • 输入：lists = []
   • 输出：[]
3. 示例 3：
   • 输入：lists = [[]]
   • 输出：[]

• 提示：
  • k == lists.length
  • $0\le k\le 10^4$
  • $0\le lists[i].length\le 500$
  • $-10^4\le lists[i][j]\le 10^4$
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 $10^4$

二、解决思路和代码

1. 解决思路

• 分析：将列表中的链表分别进行两两合并（合并两个升序链表见Leetcode21），直到列表中只有一个链表

2. 代码

    from typing import *class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def merge2Link(self, link1: Optional[ListNode], link2: Optional[ListNode]) -> Optional[ListNode]:cur = head = ListNode(val=-1)while link1 and link2:temp = link1if link1.val<=link2.val:link1 = link1.nextelse:temp = link2link2 = link2.nexttemp.next = cur.nextcur.next = tempcur = tempif link1: cur.next = link1if link2: cur.next = link2return head.nextdef mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:if len(lists)==0: return Nonewhile len(lists)>1:ls = []if len(lists)%2==1: ls.append(lists[-1])for i in range(len(lists)//2):ls.append(self.merge2Link(lists[2*i], lists[2*i+1]))lists = lsreturn lists[0]