LeetCode-链表-合并两个有序链表

LeetCode-链表-合并两个有序链表

✏️ 关于专栏：专栏用于记录 prepare for the coding test。

---

📝 合并两个有序链表

🎯题目描述

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

🔗题目链接：合并两个有序链表

🔍 输入输出示例

示例 1:

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2:

输入：l1 = [], l2 = []
输出：[]

示例 3:

输入：l1 = [], l2 = [0]
输出：[0]

🧩题目提示

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

🧪AC递归

可以直接将 mergeTwoLists 用作递归函数来合并两个有序链表：

• 递归终止条件：当其中一个链表为空时，说明不需要再继续合并，直接返回另一个非空链表即可，这个链表本身就是有序的。
• 递归处理过程：当两个链表都不为空时，比较当前节点的值。若 list1 的当前节点值较小，则将 list1.next 和 list2 继续递归合并，并将合并后的结果接在 list1 当前节点后面，返回 list1。反之，则将 list2.next 和 list1 合并，并将结果接到 list2 后，最后返回 list2。

这种方式通过递归自然地完成了节点的选择与链接，实现了有序合并。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr) return list2;if(list2 == nullptr) return list1;if(list1->val < list2->val){list1->next = mergeTwoLists(list1->next,list2);return list1;}else{list2->next = mergeTwoLists(list1,list2->next);return list2;}}
};

🧪AC迭代

我们可以先创建一个哨兵节点，它位于最终合并链表的头节点之前。这样做的好处是能统一处理流程，不用单独处理头节点或考虑链表为空的特殊情况，整体逻辑更加清晰简洁。

接下来，遍历两个链表，比较当前节点的值。若 list1 当前节点的值较小，就将其接到新链表的尾部，并让 list1 向后移动一位；反之，则将 list2 的当前节点接上，并将 list2 向后推进。若两者值相同，我们可以统一选择将 list2 的节点链接到结果链表中。

这一过程会持续进行，直到 list1 或 list2 中至少有一个遍历完毕。

当循环结束时，仍可能存在某个链表还有未处理完的节点。此时可以直接将剩下的部分追加到合并链表的末尾。

最终返回的是哨兵节点的 next 指针所指向的节点，也就是新链表的第一个有效节点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode dummy{};   //用哨兵节点简化代码逻辑auto cur = &dummy;  //cur指向新链表的末尾while(list1&&list2){if(list1->val < list2->val){cur->next = list1;list1 = list1->next;}else{cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2;return dummy.next;}
};

🌟 总结

合并两个有序链表可以通过递归或迭代两种方式来实现，思路都围绕“逐步选择较小值节点”展开。

递归法：

• 思想简洁，利用函数调用栈自动维护合并过程。
• 每次比较两个链表当前节点，选出较小值节点作为当前结果节点，继续递归合并剩余部分。
• 递归终止条件是任一链表为空，直接返回另一个链表。

迭代法：

• 更加实用，避免了递归带来的额外栈空间开销。
• 使用一个哨兵（dummy）节点作为新链表的起点，便于处理头节点和边界情况。
• 通过 cur 指针逐步向后链接较小节点，最后再拼接剩余部分。

技巧亮点：

• 哨兵节点（dummy）是处理链表问题中常见且高效的技巧，避免处理头节点的特殊逻辑。
• 两种方法都充分利用了“链表本身有序”的性质，无需新建节点，仅通过指针重新组织结构即可。