XingHuiSamaの宝藏之地

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

示例 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 均按 非递减顺序 排列

1. 算法核心思想：虚拟头节点（Dummy Node）与双指针

合并两个有序链表时，主要的边界问题在于“确定新链表的头节点”。如果直接在原链表上操作，通常需要额外的 if-else 分支来判断 list1 和 list2 谁的头节点更小，且处理空链表输入时容易出错。

引入“虚拟头节点（Dummy Node）”模式。通过人为创建一个空的初始节点（result），将其作为新链表的拼接起点。随后利用两个工作指针分别遍历原链表，每次挑出值较小的节点挂载到新链表尾部。这种做法统一了所有节点的插入逻辑。

2. 逻辑拆解

初始化操作：创建 new ListNode()，用 ans 记录该节点的物理地址以便最后返回结果。用 result 作为游标指针，负责不断向后移动并拼接新节点。
双指针同步遍历：使用 while (pre1 != NULL && pre2 != NULL) 作为循环条件。在循环体内，比较两个链表当前节点的值。
- 如果 pre1->val < pre2->val，则将 pre1 挂载到 result->next，随后 pre1 前进一步。
- 反之，则将 pre2 挂载上去，pre2 前进一步。
- 每次完成挂载后，游标 result 统一向后移动一步，准备下一次拼接。
余部直接拼接：当 while 循环因其中一个链表遍历结束而终止时，另一个链表可能仍有剩余节点。由于源链表本身已是有序结构，只需将尚未遍历完的链表头部直接赋值给 result->next，即可将剩余部分整串接入新链表。
结果返回：真实的数据节点是从虚拟头节点的下一个位置开始的，因此返回 ans->next，完成合并。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {


        ListNode* pre1 = list1;
        ListNode* pre2 = list2;

        ListNode* result =  new ListNode();
        ListNode* ans = result;

        while (pre1!=NULL && pre2!=NULL) {
            if (pre1->val < pre2->val) {
                result->next = pre1;
                pre1 = pre1->next;
                result = result->next;
            }
            else {
                result->next = pre2;
                pre2 = pre2->next;
                result = result->next;
            }
        }

        if (pre1 == NULL) {
            result->next = pre2;
        }
        else {
            result->next = pre1;
        }

        return ans->next;
    }
};

3. 复杂度分析

时间复杂度：O(M + N)。（M 和 N 分别为两个源链表的长度）。在遍历比对阶段，每次循环都会处理并接入一个节点，最多执行 M + N 次，时间消耗呈线性。
空间复杂度：O(1)。算法仅在堆内存中申请了一个虚拟头节点，以及在栈中声明了常数个指针变量。后续所有的合并操作均是通过修改原链表节点的 next 指向完成的，未申请与数据规模相关的额外空间。