【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个链表最朴素、最容易理解的思路就是“化繁为简两两合并”。我们可以把这个问题拆解为基础组件写一个辅助函数mergeTwoLists专门负责合并两个有序链表。这部分你使用了经典的Dummy 节点迭代法逻辑非常严密。主逻辑初始化一个结果链表res。然后遍历整个链表数组通过res mergeTwoLists(res, tt)像“滚雪球”一样把数组里的每一个链表依次合并到res中。 C 代码实现 (原汁原味作者版)classSolution{public:// 辅助函数合并两个升序链表ListNode*mergeTwoLists(ListNode*a,ListNode*b){// 边界处理若其中一个为空直接返回另一个if(!a||!b)returna?a:b;ListNode*dummynewListNode(0);ListNode*curdummy;while(ab){if(a-valb-val){cur-nexta;aa-next;}else{cur-nextb;bb-next;}curcur-next;}// 拼接剩余部分cur-nexta?a:b;returndummy-next;}ListNode*mergeKLists(vectorListNode*lists){ListNode*resnullptr;// 顺序合并将数组中的链表一个接一个合并到 res 中for(autott:lists){resmergeTwoLists(res,tt);}returnres;}};