题目描述与示例
题目描述
现在有一个链表数组，每个链表内都已经是升序的排序现在请你将所有的链表进行合并，返回合并后的升序链表。
输入描述
一共 n + 1行数据
第1行：一共有 n 个链表
第2~n+1行：所有的链表
输出描述
合并后的链表的所有元素
示例一
输入
3
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
解题思路
注意，本题和LeetCode23. 合并K个升序链表完全一致。
由于采用ACM模式输入，本题的输入直接用数组代替链表，故可以有两种方式进行处理：
在熟练度较高的情况下，建议使用第二种方法，以免通过笔试后，面试官查看代码。
对于K路归并问题，无论是数组还是链表，我们都可以使用优先队列来维护该过程。
代码
解法一：使用链表求解
Python
# 题目：【链表】大疆2023秋招-链表合并
# 作者：闭着眼睛学数理化
# 算法：链表/优先队列
# 代码有看不懂的地方请直接在群上提问
import heapq
# 构建链表节点类
class ListNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
# 根据数组构建链表，返回链表的头节点
def build_linked_list(nums):
nxt_node = None
# 采用逆序构建链表的方式最为简单
# 逆序遍历数组nums，构建值为num的节点node
# 同时令node指向nxt_node
for num in nums[::-1]:
node = ListNode(num, nxt_node)
nxt_node = node
return node
# 用于输出链表的函数
def print_linked_list(head):
node = head
res = list()
while(node):
res.append(node.val)
node = node.next
print(" ".join(str(val) for val in res))
# 用于对K个升序链表进行K路归并的函数
def mergeKLists(lists):
# 构建小根堆，内层元素为二元元组，由每条链表的节点值node.val和链表在lists中的索引i构成
# 注意到二元元组的排序会先按照第一个元素node.val的大小进行排序
# 故node.val最小的二元元组会位于小根堆堆顶
heap = [(node.val, i) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
# 构建哑节点，初始化当前节点cur_node为哑节点
dummyHead = ListNode(0, None)
cur_node = dummyHead
# 持续进行循环，退出循环的条件为heap为空
while (heap):
# 弹出值最小的元素，即当前lists中最小的节点
cur_min_node, idx = heapq.heappop(heap)
# 当前节点指向节点lists[idx]
cur_node.next = lists[idx]
# 当前节点cur_node前进
cur_node = cur_node.next
# 在lists中索引idx对应的节点前进
lists[idx] = lists[idx].next
# 如果前进后的节点lists[idx]不为空节点，
# 则同样按照(node.val, i)的格式压入堆中
if lists[idx]:
heapq.heappush(heap, (lists[idx].val, idx))
# 最终返回哑节点dummyHead的下一个节点，为合并后的链表的头节点
return dummyHead.next
# 输入链表条数k
k = int(input())
# 储存k条链表的数组lists
lists = list()
# 遍历k次，将输入的数组nums转化为链表head
# 再将head存入lists中
for _ in range(k):
nums = list(map(int, input().split()))
head = build_linked_list(nums)
lists.append(head)
# 调用mergeKLists()函数，得到合并后的新的头节点
final_head = mergeKLists(lists)
print_linked_list(final_head)
Java
C++
时空复杂度
时间复杂度：O(kNlogk)。考虑优先队列中的元素不超过k个，那么插入和删除的时间代价为O(logk)，这里最多有 kN个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 O(kn×logk)
空间复杂度：O(k)。这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为O(k)。
解法二：使用数组求解
Python
# 题目：【链表】大疆2023秋招-链表合并
# 作者：闭着眼睛学数理化
# 算法：数组/优先队列
# 代码有看不懂的地方请直接在群上提问
import heapq
# 用于对K个升序数组进行K路归并的函数
def mergeKLists(lists):
# 构建小根堆，内层元素为二元元组，由每个数组nums首元素的值nums[0]和其在lists中的索引i构成
# 注意到二元元组的排序会先按照第一个元素nums[0]的大小进行排序
# 故nums[0]最小的二元元组会位于小根堆堆顶
heap = [(nums[0], i) for i, nums in enumerate(lists)]
heapq.heapify(heap)
# 表示每一个数组nums进行到哪一个索引的数字idx_lst，初始化均为0
# 表示最开始时，都位于0索引的位置
# 长度为数组nums的数量，即len(lists)
idx_lst = [0] * len(lists)
ans = list()
while heap:
# 弹出值最小的元素，即当前lists中最小的数组
cur_min_num, idx = heapq.heappop(heap)
# cur_min_num为加入ans的元素
ans.append(cur_min_num)
# 在lists中索引为idx的数组lists[idx]里的索引idx_lst[idx]需要前进一步
idx_lst[idx] += 1
# 如果idx_lst[idx]前进后，没有到达
# 则同样按照(num, i)的格式压入堆中
# 其中num = lists[idx][idx_lst[idx]]
# lists[idx]为第idx个数组，选取该数组中第idx_lst[idx]个数
if idx_lst[idx] != len(lists[idx]):
num = lists[idx][idx_lst[idx]]
heapq.heappush(heap, (num, idx))
return ans
# 输入链表条数k
k = int(input())
# 储存k个链表的数组lists，此处用数组代替链表
lists = list()
# 遍历k次，直接储存数组nums
for _ in range(k):
nums = list(map(int, input().split()))
lists.append(nums)
ans = mergeKLists(lists)
print(" ".join(str(num) for num in ans))
Java
C++
