合并两个有序链表

把两个已经各自有序的链表合并成一个仍然有序的新链表 —— LeetCode 第 21 题，也是归并排序的核心子步骤。

双指针思路

两条链表各拿一个指针 a、b，谁的值小就把谁接到结果末尾，对应的指针前进一格。重复直到其中一边走完，把另一边剩下的整段直接挂上去（因为剩下的本来就有序）。

while (a != nullptr && b != nullptr) {
  if (a->val <= b->val) { tail->next = a; a = a->next; }
  else                  { tail->next = b; b = b->next; }
  tail = tail->next;
}
tail->next = (a != nullptr) ? a : b;

注意 <=（而不是 <）保证了稳定性 —— 值相等时 A 的节点排在前面。

哑结点（dummy node）

代码里 Node dummy; tail = &dummy; 是个常用技巧：先创建一个不存值的”假头”，统一处理 “结果还是空” 的边界情况，最后返回 dummy.next。免去了”是否第一个节点”的特判，代码更干净。

复杂度

• 时间：O(n + m) —— 两条链表的每个节点都只看一次
• 空间：O(1) —— 不分配新节点，直接重用原节点的指针

在动画里看什么

• 上方两行是输入链表 A（蓝）、B（红），各自的当前指针高亮
• 下方 OUT 行是结果链表，每接一个新节点就从上方掉下来
• 被消费过的节点变灰
• 结果节点的边框颜色指示它原本来自哪条链表（蓝边来自 A，红边来自 B）