一、问题描述
将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
- 输入：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)，是更高效的解法。