作为教练，我发现 LeetCode 的题目虽然逻辑清晰，但在 NOI 竞赛中，我们更倾向于考察对内存分配（指针）的底层理解或数组模拟链表的技巧。

下面是将该题适配为 NOI 风格的练习题。

题目名称：合并两个有序链表 (Merge Two Sorted Lists)

题目描述

在信息学奥赛中，高效地合并有序序列是归并排序等算法的基础。现在给定两个已经按升序排列的单链表，请你将它们合并为一个新的升序链表。

新链表要求通过拼接原有的链表节点实现，不得创建不必要的新节点。

输入格式 (Standard Input)

输入包含两行，每行表示一个链表：

• 第一行包含一个整数 $n$（表示第一个链表的长度），随后跟随 $n$ 个整数（表示链表中的元素）。
• 第二行包含一个整数 $m$（表示第二个链表的长度），随后跟随 $m$ 个整数（表示链表中的元素）。

输出格式 (Standard Output)

输出一行，包含 $n+m$ 个整数，表示合并后的升序链表元素，元素之间以空格分隔。

输入样例 1

3 1 2 4
3 1 3 4

输出样例 1

1 1 2 3 4 4

输入样例 2

0
0

输出样例 2

(空)

数据规模与约定

• $0 \le n, m \le 50$
• $-100 \le \text{节点值} \le 100$
• 两个输入链表均保证为升序。
• 时间限制：1.0s
• 内存限制：128MB

一、 预备知识点 checklist

1. 结构体 (Struct)：定义链表节点，包含 val 和 next 指针。
2. 哨兵节点 (Dummy Node)：在处理链表头部变换时，使用虚拟头节点简化逻辑。
3. 双指针 (Two Pointers)：两个指针分别指向两个序列当前处理的位置。
4. 递归与迭代：理解如何用两种方式处理重复的“比较-移动”过程。

二、 启发式思路引导

在草稿纸上，我们不要直接写代码，先画出两个序列： L1: 1 -> 2 -> 4 L2: 1 -> 3 -> 4

1. 思考： 如果我们要手动合并，第一步看哪里？
   • 比较 L1 和 L2 的头节点。谁小，谁就先接入新链表。
2. 难点： 如果其中一个链表接完了，另一个还没完，怎么办？
   • 直接把没完的那一串“挂”在已经合并好的链表末尾。
3. 技巧： 既然头节点可能会变，能不能先找个“木桩”固定住？
   • 定义一个 dummy 节点，让 curr 指针从它出发，最后返回 dummy->next。

三、 算法流程图 (Mermaid 风格)

以下是基于迭代思想的伪代码流程图：

graph TD
    A("开始合并") --> B("初始化 Dummy 节点")
    B --> C("设置指针 curr 指向 Dummy")
    C --> D{"L1 与 L2 是否均不为空?"}
    
    D -- "是" --> E{"L1 的值 <= L2 的值?"}
    E -- "是" --> F("curr 的 next 指向 L1")
    F --> G("L1 后移一步")
    E -- "否" --> H("curr 的 next 指向 L2")
    H --> I("L2 后移一步")
    
    G --> J("curr 后移一步")
    I --> J
    J --> D
    
    D -- "否" --> K{"L1 为空吗?"}
    K -- "是" --> L("curr 的 next 指向 L2")
    K -- "否" --> M("curr 的 next 指向 L1")
    
    L --> N("返回 Dummy 的 Next 节点")
    M --> N
    N --> O("结束")

四、 复杂度分析思考过程

• 时间复杂度分析：

  • 我们需要遍历两个链表的所有节点吗？
  • 是的。每次循环我们都会将 L1 或 L2 中的一个节点接入结果，总共执行 $n+m$ 次操作。
  • 结论：时间复杂度为 $O(n+m)$。

• 空间复杂度分析：

  • 如果我们使用迭代法（如上图），我们只额外申请了 dummy 和 curr 两个指针的空间。
  • 结论：空间复杂度为 $O(1)$。
  • 注意：如果你使用递归实现，由于系统栈的深度，空间复杂度会变为 $O(n+m)$。在 NOI 竞赛中，若数据范围极大，需警惕栈溢出。

五、 读题关键词与坑点总结

1. “通过拼接原有的链表节点实现”：
   • 这意味着不要在循环里 new Node(val)，而是直接操作指针指向。
2. “升序”：
   • 这是双指针合并的前提。如果题目给的是乱序，则需要先排序。
3. 空链表处理：
   • 读题时要看清数据范围（$0 \le n, m$）。如果 $n=0$，你的代码会不会解引用空指针（Null Pointer Assignment）？
4. C++14 建议：
   • 在竞赛中，建议手动管理内存。虽然 LeetCode 环境不需要你 delete，但在某些要求严格的工程题中，养成清理内存的习惯很重要。
   • 使用 nullptr 而非 NULL。