23 合并 K 个升序链表

2026年7月13日

一、题目

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

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

![](/leetcode/assets/23.合并 K 个升序链表.png)

二、题解

方法一：优先队列（小根堆）

思路：优先队列、链表。

1. 核心思路

由于每个链表本身都是升序排列的，所以每个链表当前的头节点，就是该链表剩余节点中的最小值。

我们可以将所有非空链表的头节点放入一个小根堆中，小根堆能够快速找到当前所有节点中的最小节点。

核心思想是：

将每个非空链表的头节点加入小根堆；
每次从堆中取出值最小的节点，将其连接到结果链表；
如果取出的节点还有下一个节点，就将下一个节点加入小根堆；
重复以上操作，直到小根堆为空。

例如：

链表 1：1 -> 4 -> 5
链表 2：1 -> 3 -> 4
链表 3：2 -> 6

首先将三个链表的头节点加入小根堆：

堆中节点：1、1、2

取出最小节点 1 后，将它连接到结果链表，并把它的下一个节点 4 加入堆中。

不断重复这个过程，最终得到：

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

2. 具体步骤

创建一个小根堆，按照链表节点的值从小到大排序。
遍历链表数组，将每个非空链表的头节点加入小根堆。
创建虚拟头节点 dummy，用于构建结果链表。
每次从小根堆中取出值最小的节点。
将取出的节点连接到结果链表末尾。
如果该节点存在下一个节点，就将下一个节点加入小根堆。
当小根堆为空时，所有节点都已经完成合并。
返回 dummy.next。

3. 关键逻辑

while (!heap.isEmpty()) {
    // 取出当前值最小的节点
    ListNode minNode = heap.poll();

    // 将最小节点连接到结果链表
    current.next = minNode;
    current = current.next;

    // 将该节点的下一个节点加入小根堆
    if (minNode.next != null) {
        heap.offer(minNode.next);
    }
}

解释：

heap.poll() 每次取出当前所有链表中值最小的节点；
取出的节点就是结果链表中下一个应该连接的节点；
如果该节点后面还有节点，那么它的下一个节点就成为原链表新的候选节点；
将新的候选节点加入小根堆，继续参与比较；
小根堆中最多只会同时保存每个链表的一个候选节点。

4. 代码

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *
 *     ListNode() {}
 *
 *     ListNode(int val) {
 *         this.val = val;
 *     }
 *
 *     ListNode(int val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 1. 处理特殊情况
        if (lists == null || lists.length == 0) {
            return null;
        }

        // 2. 创建小根堆，节点值越小，优先级越高
        PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (node1, node2) -> Integer.compare(node1.val, node2.val)
        );

        // 3. 将每个非空链表的头节点加入小根堆
        for (ListNode head : lists) {
            if (head != null) {
                heap.offer(head);
            }
        }

        // 4. 创建虚拟头节点，用于构建结果链表
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // 5. 每次取出当前值最小的节点
        while (!heap.isEmpty()) {
            ListNode minNode = heap.poll();

            // 将最小节点连接到结果链表
            current.next = minNode;
            current = current.next;

            // 如果该节点还有下一个节点，将其加入小根堆
            if (minNode.next != null) {
                heap.offer(minNode.next);
            }
        }

        // 6. 返回合并后链表的头节点
        return dummy.next;
    }
}

5. 复杂度分析

设所有链表的节点总数为 N，链表数量为 k。

时间复杂度： $O(N \log k)$

说明：

每个节点都会进入小根堆一次，并从小根堆中取出一次。

小根堆中最多保存 k 个节点，每次插入或删除操作的时间复杂度为 $O(\log k)$ ，所以总时间复杂度为 $O(N \log k)$ 。

空间复杂度： $O(k)$

说明：

小根堆中最多同时保存 k 个链表的候选节点，因此空间复杂度为 $O(k)$ 。

方法二：分治合并

思路：分治、归并排序、合并两个升序链表。

1. 核心思路

方法一使用小根堆不断选出最小节点，而方法二通过分治，将 k 个链表不断拆分成更小的范围。

当一个范围中只剩下一个链表时，直接返回该链表。

然后将左右两部分分别合并完成，再使用“合并两个升序链表”的方法，将左右两个有序链表合并。

这种方法的核心是：

将链表数组从中间分为左右两部分；
递归合并左半部分的链表；
递归合并右半部分的链表；
最后合并左右两个升序链表。

例如有四个链表：

L1、L2、L3、L4

第一层拆分：

L1、L2        L3、L4

第二层拆分：

L1    L2      L3    L4

开始向上合并：

merge(L1, L2)
merge(L3, L4)

最后再合并：

merge(
    merge(L1, L2),
    merge(L3, L4)
)

2. 具体步骤

如果链表数组为空，直接返回 null。
使用 left 和 right 表示当前需要合并的链表范围。
如果 left == right，说明当前范围中只有一个链表，直接返回。
计算中间位置 mid，将当前范围分成左右两部分。
递归合并左半部分，得到一个升序链表。
递归合并右半部分，得到一个升序链表。
使用合并两个升序链表的方法，将左右两个结果合并。
返回最终合并完成的链表。

3. 关键逻辑

private ListNode mergeRange(ListNode[] lists, int left, int right) {
    // 当前范围中只有一个链表
    if (left == right) {
        return lists[left];
    }

    int mid = left + (right - left) / 2;

    // 分别合并左右两部分
    ListNode leftList = mergeRange(lists, left, mid);
    ListNode rightList = mergeRange(lists, mid + 1, right);

    // 合并两个升序链表
    return mergeTwoLists(leftList, rightList);
}

解释：

如果 left == right，说明不需要继续拆分，直接返回当前链表；
否则将链表数组分成左右两个范围；
左右两个范围分别合并完成后，都会得到一个升序链表；
最后只需要合并这两个升序链表；
每次将问题规模缩小一半，因此递归层数约为 $\log k$ 。

合并两个升序链表的关键逻辑：

while (list1 != null && list2 != null) {
    if (list1.val <= list2.val) {
        current.next = list1;
        list1 = list1.next;
    } else {
        current.next = list2;
        list2 = list2.next;
    }

    current = current.next;
}

解释：

如果 list1.val <= list2.val，说明 list1 当前节点更小，将它连接到结果链表；
否则说明 list2 当前节点更小，将 list2 当前节点连接到结果链表；
每连接一个节点，就将对应链表的指针向后移动；
当其中一个链表为空时，将另一个链表的剩余部分直接连接到结果链表。

4. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *
 *     ListNode() {}
 *
 *     ListNode(int val) {
 *         this.val = val;
 *     }
 *
 *     ListNode(int val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 1. 处理特殊情况
        if (lists == null || lists.length == 0) {
            return null;
        }

        // 2. 分治合并整个链表数组
        return mergeRange(lists, 0, lists.length - 1);
    }

    /**
     * 合并 lists[left...right] 范围内的所有链表
     */
    private ListNode mergeRange(ListNode[] lists, int left, int right) {
        // 当前范围中只有一个链表，直接返回
        if (left == right) {
            return lists[left];
        }

        // 防止 left + right 发生整数溢出
        int mid = left + (right - left) / 2;

        // 递归合并左半部分
        ListNode leftList = mergeRange(lists, left, mid);

        // 递归合并右半部分
        ListNode rightList = mergeRange(lists, mid + 1, right);

        // 合并左右两个升序链表
        return mergeTwoLists(leftList, rightList);
    }

    /**
     * 合并两个升序链表
     */
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建虚拟头节点，方便构建结果链表
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // 比较两个链表的当前节点
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }

            current = current.next;
        }

        // 将未遍历完的链表直接连接到结果链表末尾
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        return dummy.next;
    }
}

5. 复杂度分析

设所有链表的节点总数为 N，链表数量为 k。

时间复杂度： $O(N \log k)$

说明：

分治过程共有大约 $\log k$ 层。

在每一层中，所有链表节点都会被遍历和合并一次，因此每层的时间复杂度为 $O(N)$ 。

所以总时间复杂度为：

O(N) × O(log k) = O(N log k)

空间复杂度： $O(\log k)$

说明：

分治递归的深度约为 $\log k$ ，额外空间主要来自递归调用栈，因此空间复杂度为 $O(\log k)$ 。

合并链表时直接复用原有链表节点，没有创建保存所有节点的新数组。

一、题目

二、题解

方法一：优先队列（小根堆）

1. 核心思路

2. 具体步骤

3. 关键逻辑

4. 代码

5. 复杂度分析

方法二：分治合并

1. 核心思路

2. 具体步骤

3. 关键逻辑

4. 代码

5. 复杂度分析

评论