合并两个有序链表：双指针迭代法实现（C++）

一、问题描述

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

示例：

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

二、解题思路

1. 递推关系分析

合并两个升序链表的核心是逐个比较两个链表的当前节点值，选择较小的节点接入新链表，直到其中一个链表遍历完毕。

• 若链表 l1 的当前节点值 ≤ 链表 l2 的当前节点值，将 l1 的当前节点接入新链表，l1 指针后移；
• 若链表 l2 的当前节点值更小，将 l2 的当前节点接入新链表，l2 指针后移；
• 当其中一个链表遍历完成后，直接将另一个链表的剩余节点拼接至新链表末尾即可。

为简化头节点为空的边界处理，引入虚拟头节点，避免单独处理首个节点的选择逻辑。

2. 算法选择

• 递归法：通过递归调用合并剩余节点，代码简洁但会产生递归调用栈，空间复杂度为 O (m+n)（m、n 为两个链表的长度），且递归深度较大时可能出现栈溢出；
• 双指针迭代法：用指针遍历两个链表并拼接节点，仅使用常数级额外空间，时间复杂度为 O (m+n)，空间复杂度为 O (1)，是更高效的解法。

三、C++ 代码实现