题解 | 合并k个已排序的链表

1、解题思路

1. 问题分析：每个链表已经是升序排列的。我们需要将这些链表合并成一个整体升序的链表。
2. 方法选择：分治法：将 k 个链表两两合并，逐步减少链表数量，直到合并成一个链表。优先队列（最小堆）：将所有链表的头节点放入最小堆，每次取出最小的节点，并将其下一个节点加入堆中，直到堆为空。
3. 复杂度分析：分治法：每次合并两个链表的时间为 O(n)，共进行 log k 次合并，总时间为 O(n log k)。优先队列：每次插入和取出操作的时间为 O(log k)，共进行 n 次操作，总时间为 O(n log k)。
4. 选择实现：这里选择 优先队列 的方法，因为代码更简洁且易于理解。

2、代码实现

C++

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <queue>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        // 定义优先队列的比较函数，按节点值升序排列
        auto cmp = [](ListNode * a, ListNode * b) {
            return a->val > b->val;  // 小顶堆，值小的优先级高
        };
        // 创建优先队列，存储链表节点指针
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

        // 将每个链表的头节点加入优先队列
        for (ListNode* list : lists) {
            if (list != nullptr) {    // 确保链表非空
                pq.push(list);        // 将非空链表的头节点加入队列
            }
        }

        // 创建虚拟头节点，用于简化链表操作
        ListNode dummy(0);
        ListNode* tail = &dummy;      // 尾指针用于连接节点

        // 循环处理优先队列，直到队列为空
        while (!pq.empty()) {
            ListNode* node = pq.top();    // 取出当前最小节点
            pq.pop();                     // 移除已取出的节点
            tail->next = node;            // 将最小节点连接到结果链表
            tail = tail->next;            // 移动尾指针到新连接的节点
            // 如果当前节点还有后续节点，将后续节点加入队列
            if (node->next != nullptr) {
                pq.push(node->next);
            }
        }

        // 返回合并后的链表头节点（跳过虚拟头节点）
        return dummy.next;
    }
};

Java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        // 创建优先队列，按节点值升序排列
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 将每个链表的头节点加入优先队列
        for (ListNode list : lists) {
            if (list != null) {      // 确保链表非空
                pq.offer(list);      // 将非空链表的头节点加入队列
            }
        }

        // 创建虚拟头节点，用于简化链表操作
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;       // 尾指针用于连接节点

        // 循环处理优先队列，直到队列为空
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();   // 取出当前最小节点
            tail.next = node;            // 将最小节点连接到结果链表
            tail = tail.next;            // 移动尾指针到新连接的节点
            // 如果当前节点还有后续节点，将后续节点加入队列
            if (node.next != null) {
                pq.offer(node.next);
            }
        }

        // 返回合并后的链表头节点（跳过虚拟头节点）
        return dummy.next;
    }
}

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param lists ListNode类一维数组
# @return ListNode类
#
import heapq  # 使用堆模块实现最小堆

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # write code here
        # 创建最小堆，存储三元组（节点值, 链表索引, 节点）
        # 使用链表索引作为第二比较项，避免节点值相同时比较节点
        min_heap = []
        for idx, node in enumerate(lists):
            if node:  # 确保链表非空
                heapq.heappush(min_heap, (node.val, idx, node))

        # 创建虚拟头节点，用于简化链表操作
        dummy = ListNode(0)
        tail = dummy  # 尾指针用于连接节点

        # 循环处理最小堆，直到堆为空
        while min_heap:
            val, idx, node = heapq.heappop(min_heap)  # 取出当前最小节点
            tail.next = node  # 将最小节点连接到结果链表
            tail = tail.next  # 移动尾指针到新连接的节点
            # 如果当前节点还有后续节点，将后续节点加入堆
            if node.next:
                heapq.heappush(min_heap, (node.next.val, idx, node.next))

        # 返回合并后的链表头节点（跳过虚拟头节点）
        return dummy.next

3、复杂度分析

1. 时间复杂度：每个节点被插入和取出堆一次，每次操作时间为 O(log k)，总时间为 O(n log k)，满足题目要求。
2. 空间复杂度：堆的大小最多为 k，因此空间复杂度为 O(k)。