题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]示例 2输入l1 [], l2 []输出[]示例 3输入l1 [], l2 [0]输出[0]解题思路我的思路是先把两个链表的值按顺序合并到一个 vector再用 vector 的值新建链表。具体步骤处理边界如果有一个链表为空直接返回另一个双指针合并用list1和list2逐个比较把较小的值存入value处理剩余把没遍历完的链表剩余部分全部存入value重建链表遍历value逐个new ListNode连接成新链表用例子走一遍list1 1 - 2 - 4,list2 1 - 3 - 4步骤比较存入 value11 11list1 后移22 11list2 后移32 32list1 后移44 33list2 后移54 44list1 后移6list1 为空4list2 后移value [1, 1, 2, 3, 4, 4]重建链表1 - 1 - 2 - 3 - 4 - 4✅代码实现class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(list1nullptrlist2nullptr) return list1; if(list1nullptr) return list2; if(list2nullptr) return list1; vectorint value; while(list1!nullptrlist2!nullptr){ if(list1-vallist2-val){ value.push_back(list1-val); list1list1-next; } else{ value.push_back(list2-val); list2list2-next; } } if(list1nullptr){ while(list2!nullptr){ value.push_back(list2-val); list2list2-next; } } else{ while(list1!nullptr){ value.push_back(list1-val); list1list1-next; } } ListNode *head nullptr; ListNode *tail nullptr; for (int x : value) { ListNode *node new ListNode(x); if (head nullptr) { head node; tail node; } else { tail-next node; tail node; } } return head; } };复杂度分析维度复杂度说明时间复杂度O(n m)遍历两个链表各一次重建链表一次空间复杂度O(n m)vector 存储所有值 新建链表节点问题额外使用了 O(n m) 的空间看了题解后发现这道题的标准解法可以做到O(1) 空间原地合并。最优解法原地合并O(1) 空间核心思路不需要 vector直接修改指针把两个链表的节点按顺序串起来。用虚拟头结点dummy node简化操作dummy是虚拟头结点不存实际值curr指向当前合并后的最后一个节点每次比较list1和list2把较小的节点接到curr-next最后把剩余的链表直接接上具体过程示例list1 1 - 2 - 4,list2 1 - 3 - 4dummy - null curr dummy 第1步: 1 1, 接 list1 的 1 dummy - 1 curr 1, list1 2 第2步: 2 1, 接 list2 的 1 dummy - 1 - 1 curr 1, list2 3 第3步: 2 3, 接 list1 的 2 dummy - 1 - 1 - 2 curr 2, list1 4 第4步: 4 3, 接 list2 的 3 dummy - 1 - 1 - 2 - 3 curr 3, list2 4 第5步: 4 4, 接 list1 的 4 dummy - 1 - 1 - 2 - 3 - 4 curr 4, list1 null 第6步: list1 为空, 接 list2 的剩余部分 dummy - 1 - 1 - 2 - 3 - 4 - 4 返回 dummy-next ✅代码实现class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *dummy new ListNode(0); // 虚拟头结点 ListNode *curr dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { curr-next list1; list1 list1-next; } else { curr-next list2; list2 list2-next; } curr curr-next; } // 接上剩余的链表 curr-next (list1 ! nullptr) ? list1 : list2; return dummy-next; } };复杂度分析维度复杂度时间复杂度O(n m)遍历两个链表各一次空间复杂度O(1)只用了几个指针不算虚拟头结点两种方法对比对比维度我的方法vector重建原地合并时间复杂度O(n m)O(n m)空间复杂度O(n m)O(1)是否修改原链表❌ 不修改✅ 修改是否需要新建节点✅ 需要 new nm 个❌ 不需要代码复杂度较长极简推荐度⭐⭐⭐⭐⭐⭐⭐⭐关键细节1. 虚拟头结点的作用ListNode *dummy new ListNode(0); ListNode *curr dummy;dummy不存实际值只是方便返回结果如果不使用 dummy需要单独处理第一个节点的情况代码会复杂很多返回时返回dummy-next即可2. 为什么最后直接接剩余部分curr-next (list1 ! nullptr) ? list1 : list2;因为list1和list2本身已经是有序的剩余的部分不需要再逐个比较直接接上即可。总结要点说明我的代码时间 O(nm)空间 O(nm)正确但空间不是最优最优解法虚拟头结点 原地合并时间 O(nm)空间 O(1)核心思想逐个比较把较小的节点接到结果链表关键技巧虚拟头结点简化边界处理这道题是链表合并的经典题掌握后可以解决很多链表题比如合并 K 个有序链表、排序链表等。