合并两个有序链表

怎样从“合并有序链表 1→2→4 与 1→3→4 为一条升序链表。”推导出 链表 · 归并，并证明每次状态变化都不会漏掉答案？

中心结论：dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。

合并有序链表 1→2→4 与 1→3→4 为一条升序链表。

在本站主例中，合并有序链表 1→2→4 与 1→3→4 为一条升序链表。

算法最终需要得到或观察：合并结果 1→1→2→3→4→4。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 l1/l2 当前头、tail 结果尾、已接结点数。
3. 3转移每一步按照 dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。
4. 4收尾读取 合并结果 1→1→2→3→4→4。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：l1/l2 当前头、tail 结果尾、已接结点数。

dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。

执行过程中持续维护：l1/l2 当前头、tail 结果尾、已接结点数。

正确性依赖以下不变量：结果链表始终有序,且包含两链全部结点。

面试时可以压缩为：迭代 dummy:比较 l1/l2 头,较小者接到 tail 并前移;一方空则接另一方。

落到当前题，执行机制可以压缩为：dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入合并有序链表 1→2→4 与 1→3→4 为一条升序链表。 因为：dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。
2. 2dummy 结点 + 双指针比较两个链表当前结点。 因为：归并排序的链表版。
3. 3取 b[0]=1较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5取 a[1]=2较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
6. 6取 b[1]=3较小者接入结果链,对应指针前进。 因为：保持结果链表有序。
7. 7合并完成剩余段直接接上。 因为：O(m+n) 一次扫描。
8. 8收尾与复杂度合并结果 1→1→2→3→4→4。 因为：时间 O(m+n) · 空间 O(1)。dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	}
	l2.Next = mergeTwoLists(l1, l2.Next)
	return l2
}

func main() {
    // 1. 主例
    //    输入：mode="merge-two", values=[1,2,4], valuesB=[1,3,4]
    //    期望：合并结果 1→1→2→3→4→4。
    //
    // 2. 失败 / 未命中
    //    检查：循环条件写 l1&&l2 结束后忘记接剩余链。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC23 合并 K 个链表；LC148 排序链表
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意合并有序链表 1→2→4 与 1→3→4 为一条升序链表。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化dummy 尾指针每次接较小头结点,较短链先耗尽后把剩余直接接上。
4. 4证明结果链表始终有序,且包含两链全部结点。
5. 5复杂度时间 O(m+n)，空间 O(1)