企业官网建设流程全解析

题目描述：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 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 的值新建链表。

具体步骤：

1. 处理边界：如果有一个链表为空，直接返回另一个

2. 双指针合并：用list1和list2逐个比较，把较小的值存入value

3. 处理剩余：把没遍历完的链表剩余部分全部存入value

4. 重建链表：遍历value，逐个new ListNode，连接成新链表

用例子走一遍：

list1 = 1 -> 2 -> 4,list2 = 1 -> 3 -> 4

value = [1, 1, 2, 3, 4, 4]

重建链表：1 -> 1 -> 2 -> 3 -> 4 -> 4✅

代码实现：

class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(list1==nullptr&&list2==nullptr) return list1; if(list1==nullptr) return list2; if(list2==nullptr) return list1; vector<int> value; while(list1!=nullptr&&list2!=nullptr){ if(list1->val<=list2->val){ value.push_back(list1->val); list1=list1->next; } else{ value.push_back(list2->val); list2=list2->next; } } if(list1==nullptr){ while(list2!=nullptr){ value.push_back(list2->val); list2=list2->next; } } else{ while(list1!=nullptr){ value.push_back(list1->val); list1=list1->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(1) 空间（原地合并）。

最优解法：原地合并（O(1) 空间）

核心思路：

不需要 vector，直接修改指针，把两个链表的节点按顺序串起来。

用虚拟头结点（dummy node）简化操作：

• dummy是虚拟头结点，不存实际值

• curr指向当前合并后的最后一个节点

• 每次比较list1和list2，把较小的节点接到curr->next

• 最后把剩余的链表直接接上

具体过程示例：

list1 = 1 -> 2 -> 4,list2 = 1 -> 3 -> 4

dummy -> 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; } };

复杂度分析：

两种方法对比：

关键细节：

1. 虚拟头结点的作用

ListNode *dummy = new ListNode(0); ListNode *curr = dummy;

• dummy不存实际值，只是方便返回结果

• 如果不使用 dummy，需要单独处理"第一个节点"的情况，代码会复杂很多

• 返回时返回dummy->next即可

2. 为什么最后直接接剩余部分？

curr->next = (list1 != nullptr) ? list1 : list2;

因为list1和list2本身已经是有序的，剩余的部分不需要再逐个比较，直接接上即可。

总结：

这道题是链表合并的经典题，掌握后可以解决很多链表题（比如合并 K 个有序链表、排序链表等）。