23. 合并 K 个升序链表

力扣题目链接 (opens new window)

题目描述

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

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

示例 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

思路

这道题是 21.合并两个有序链表 的升级版。

如果只有两个链表，直接双指针合并就行。但现在有 K 个链表，怎么办？

方法一：暴力合并（不推荐）

最直观的想法是：先合并前两个链表，得到结果后再和第三个合并，以此类推。

但这样效率很低。假设每个链表长度为 n，合并第一个和第二个需要 2n 次比较，合并结果和第三个需要 3n 次比较，……最后总共需要 n + 2n + 3n + ... + kn = O(k²n) 次比较。

方法二：优先队列（小顶堆）

核心思想：每次从 K 个链表的当前节点中选出最小的那个。

怎么快速找到最小值？用优先队列（小顶堆）。

具体流程：

1. 将 K 个链表的头节点都放入小顶堆
2. 每次从堆中取出最小的节点，接到结果链表后面
3. 如果这个节点有 next，把 next 放入堆中
4. 重复步骤 2-3，直到堆为空

时间复杂度分析：

• 总共有 kn 个节点
• 每个节点入堆出堆各一次，每次堆操作 O(log k)
• 总时间复杂度 O(kn log k)

这比暴力合并的 O(k²n) 快多了。

方法三：分治归并

还记得 148.排序链表 中的归并排序吗？

我们可以用同样的分治思想：

1. 将 K 个链表两两配对，合并成 K/2 个链表
2. 再将 K/2 个链表两两配对，合并成 K/4 个链表
3. 不断二分，直到只剩一个链表

时间复杂度分析：

• 每一层合并，所有节点都会被遍历一次，O(kn)
• 总共 log k 层
• 总时间复杂度 O(kn log k)

分治法和优先队列时间复杂度一样，但分治法空间复杂度更优（O(log k) 递归栈 vs O(k) 堆空间）。

模拟过程

以示例 1 为例：[[1,4,5],[1,3,4],[2,6]]

优先队列法

初始状态：将三个链表的头节点放入小顶堆

第一步：取出堆顶 1（链表1），将它的 next（4）放入堆

结果链表：1

第二步：取出堆顶 1（链表2），将它的 next（3）放入堆

结果链表：1 → 1

第三步：取出堆顶 2（链表3），将它的 next（6）放入堆

结果链表：1 → 1 → 2

以此类推，直到堆为空。

解题代码

优先队列法

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 定义小顶堆的比较函数
        auto cmp = [](ListNode* a, ListNode* b) {
            return a->val > b->val; // 注意是大于号，构建小顶堆
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        
        // 将所有链表的头节点放入堆中
        for (ListNode* head : lists) {
            if (head != nullptr) {
                pq.push(head);
            }
        }
        
        ListNode* dummyHead = new ListNode(0);
        ListNode* cur = dummyHead;
        
        // 每次取出堆顶最小节点
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            
            cur->next = node;
            cur = cur->next;
            
            // 如果该节点有 next，将 next 放入堆
            if (node->next != nullptr) {
                pq.push(node->next);
            }
        }
        
        return dummyHead->next;
    }
};

分治归并法

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeLists(lists, 0, lists.size() - 1);
    }
    
private:
    // 分治合并 lists[left...right] 区间的链表
    ListNode* mergeLists(vector<ListNode*>& lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        
        int mid = left + (right - left) / 2;
        ListNode* l1 = mergeLists(lists, left, mid);
        ListNode* l2 = mergeLists(lists, mid + 1, right);
        
        return mergeTwoLists(l1, l2);
    }
    
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* cur = dummyHead;
        
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        
        cur->next = (l1 != nullptr) ? l1 : l2;
        return dummyHead->next;
    }
};

复杂度分析

优先队列法：

• 时间复杂度：O(kn log k)，其中 n 是每个链表的平均长度
• 空间复杂度：O(k)，堆中最多存储 k 个节点

分治归并法：

• 时间复杂度：O(kn log k)
• 空间复杂度：O(log k)，递归调用栈

其他语言

Python3

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        import heapq
        
        # 小顶堆，存储 (节点值, 索引, 节点)
        # 索引用于打破值相同时的比较
        heap = []
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i, head))
        
        dummy = ListNode(0)
        cur = dummy
        
        while heap:
            val, idx, node = heapq.heappop(heap)
            cur.next = node
            cur = cur.next
            
            if node.next:
                heapq.heappush(heap, (node.next.val, idx, node.next))
        
        return dummy.next

Java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 优先队列，按节点值升序
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        // 将所有头节点放入堆
        for (ListNode head : lists) {
            if (head != null) {
                pq.offer(head);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            cur.next = node;
            cur = cur.next;
            
            if (node.next != null) {
                pq.offer(node.next);
            }
        }
        
        return dummy.next;
    }
}

Go

import "container/heap"

type MinHeap []* ListNode

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    h := &MinHeap{}
    heap.Init(h)
    
    // 将所有头节点放入堆
    for _, head := range lists {
        if head != nil {
            heap.Push(h, head)
        }
    }
    
    dummy := &ListNode{}
    cur := dummy
    
    for h.Len() > 0 {
        node := heap.Pop(h).(*ListNode)
        cur.Next = node
        cur = cur.Next
        
        if node.Next != nil {
            heap.Push(h, node.Next)
        }
    }
    
    return dummy.Next
}

JS

var mergeKLists = function(lists) {
    // 使用数组模拟小顶堆
    const heap = [];
    
    // 将所有头节点放入堆
    for (let head of lists) {
        if (head) {
            heap.push(head);
        }
    }
    
    // 堆化
    for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) {
        heapify(heap, i);
    }
    
    const dummy = new ListNode(0);
    let cur = dummy;
    
    while (heap.length > 0) {
        // 取出堆顶
        const node = heap[0];
        heap[0] = heap[heap.length - 1];
        heap.pop();
        if (heap.length > 0) {
            heapify(heap, 0);
        }
        
        cur.next = node;
        cur = cur.next;
        
        if (node.next) {
            heap.push(node.next);
            // 上浮
            let idx = heap.length - 1;
            while (idx > 0) {
                let parent = Math.floor((idx - 1) / 2);
                if (heap[parent].val <= heap[idx].val) break;
                [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
                idx = parent;
            }
        }
    }
    
    return dummy.next;
};

function heapify(heap, i) {
    let smallest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    
    if (left < heap.length && heap[left].val < heap[smallest].val) {
        smallest = left;
    }
    if (right < heap.length && heap[right].val < heap[smallest].val) {
        smallest = right;
    }
    
    if (smallest !== i) {
        [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
        heapify(heap, smallest);
    }
}

与代码随想录联系

这道题综合了多个知识点：

1. 合并两个有序链表 — 在 21.合并两个有序链表 中是基础操作
2. 优先队列（堆） — 在代码随想录 堆章节 有详细讲解
3. 分治思想 — 在 148.排序链表 中用归并排序展示过

面试中如果时间充裕，建议两种方法都掌握。优先队列法更直观，分治法空间复杂度更优。

很多录友做这道题的时候，会卡在"如何从 K 个节点中快速找最小值"这一步。想清楚这个问题的本质，就应该想到堆了。