🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

题目描述

将两个升序的单链表合并为一个新的升序单链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的，不允许额外创建新节点，只能复用原节点。

示例：

plaintext

输入：list1 = [1,2,4], list2 = [1,3,4]
输出：[1,1,2,3,4,4]

解题思路

这道题是链表操作的经典入门题，核心思路是双指针遍历 + 哨兵节点（哑节点）：

1. 双指针：同时遍历两个有序链表，每次比较两个指针指向节点的值，将较小的节点接入新链表；
2. 哨兵节点：创建一个临时虚拟节点，避免处理头节点为空的边界情况，让代码更简洁；
3. 拼接剩余节点：当其中一个链表遍历完毕后，直接将另一个链表的剩余部分接到结果链表尾部。

整个过程时间复杂度 O (n+m)（n、m 为两个链表长度，每个节点仅遍历一次），空间复杂度 O (1)（仅使用常数个临时指针）。

完整代码解析

我直接给出最优解代码，逐行讲解每一步的作用：

cpp

运行

/**
 * 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 temp;       // 1. 哨兵节点（哑节点），不存储实际数据，仅用于简化头节点处理
        ListNode* cur = &temp;// 2. 工作指针，始终指向结果链表的最后一个节点
      
        // 3. 同时遍历两个链表，直到其中一个遍历完毕
        while (list1 && list2) {
            // 比较节点值，将较小的节点接到结果链表尾部
            if(list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next; // 移动原链表指针
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next; // 移动工作指针，始终指向新链表尾部
        }
      
        // 4. 拼接剩余节点：一个链表空了，直接接另一个的剩余部分
        cur->next = list1 ? list1 : list2;
      
        // 5. 哨兵节点的next就是最终合并后的链表头节点
        return temp.next;
    }
};

核心知识点详解

1. 哨兵节点（temp）

   • 作用：解决「新链表头节点为空」的边界问题，不用单独判断第一个节点该选谁；
   • 最终返回 temp.next，就是合并后链表的真实头节点。

2. 工作指针（cur）

   • 始终跟踪结果链表的末尾，方便后续节点直接拼接，不用每次遍历找尾部。

3. 循环逻辑

   • 只有 list1 和 list2 都不为空时才进入循环；
   • 每次取较小值节点接入，保证新链表始终有序。

4. 剩余节点拼接

   • 因为两个原链表都是有序的，剩余部分一定是递增的，直接拼接即可，无需再排序。

代码运行演示

以 list1=[1,2,4]、list2=[1,3,4] 为例：

1. 初始：temp -> null，cur=temp，list1=1，list2=1；
2. 第一次比较：1=1，取 list2，temp->1->3->4，cur=1，list2=3；
3. 第二次比较：1<3，取 list1，temp->1->1->2->4，cur=1，list1=2；
4. 第三次比较：2<3，取 list1，temp->1->1->2->4，cur=2，list1=4；
5. 第四次比较：4>3，取 list2，temp->1->1->2->3->4，cur=3，list2=4；
6. 第五次比较：4=4，取 list2，temp->1->1->2->3->4->4，cur=4，list2=null；
7. 退出循环，拼接 list1 剩余节点（已空），最终返回 temp.next。

为什么推荐这个写法？

1. 极简高效：无冗余代码，时间 / 空间复杂度均为最优；
2. 无边界问题：哨兵节点完美处理空链表、单节点链表等特殊情况；
3. 易读易写：逻辑清晰，面试手写代码几乎不会出错。

总结

合并两个有序链表是链表基础操作，核心掌握两点：✅ 双指针遍历 比较取值✅ 哨兵节点 简化边界处理

这个解法是面试高频标准答案，吃透它，链表基础操作就稳了！