【Hot 100 刷题计划】 LeetCode 23. 合并 K 个升序链表 | C++ 顺序合并

LeetCode 23. 合并 K 个升序链表

📌 题目描述

题目级别：困难 (Hard)

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

• 示例 1:
  输入：lists = [[1,4,5],[1,3,4],[2,6]]
  输出：[1,1,2,3,4,4,5,6]

💡 破题思路：顺序合并 (Sequential Merge)

合并KKK个链表最朴素、最容易理解的思路就是：“化繁为简，两两合并”。

我们可以把这个问题拆解为：

1. 基础组件：写一个辅助函数mergeTwoLists，专门负责合并两个有序链表。这部分你使用了经典的Dummy 节点迭代法，逻辑非常严密。
2. 主逻辑：初始化一个结果链表res。然后遍历整个链表数组，通过res = mergeTwoLists(res, tt)，像“滚雪球”一样，把数组里的每一个链表依次合并到res中。

💻 C++ 代码实现 (原汁原味作者版)

classSolution{public:// 辅助函数：合并两个升序链表ListNode*mergeTwoLists(ListNode*a,ListNode*b){// 边界处理：若其中一个为空，直接返回另一个if(!a||!b)returna?a:b;ListNode*dummy=newListNode(0);ListNode*cur=dummy;while(a&&b){if(a->val<b->val){cur->next=a;a=a->next;}else{cur->next=b;b=b->next;}cur=cur->next;}// 拼接剩余部分cur->next=a?a:b;returndummy->next;}ListNode*mergeKLists(vector<ListNode*>&lists){ListNode*res=nullptr;// 顺序合并：将数组中的链表一个接一个合并到 res 中for(autott:lists){res=mergeTwoLists(res,tt);}returnres;}};