合并两个有序序列
各用一个指针遍历两个列表
合并两个有序序列 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
合并步骤
给定两个已排序的列表，请将它们合并为一个已排序的列表。合并是归并排序的核心，也在各种场景中出现。🔗
两个输入，各有一个指针
为每个列表分配一个指针，两个指针都从索引 0 开始。您将让它们一起向前移动，绝不后退。
i = 0
j = 0始终取较小值
每一步比较两个列表的首元素。将较小的那个添加到结果中，因为按排序顺序它一定应该排在下一个位置。
移动胜出的指针
取出一个值后，只对该值所属列表的指针执行 advance。另一个列表仍然保留着它的最小元素。
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1主循环
当两个列表都还有元素时，继续合并。只要其中一个列表耗尽，比较就不再有意义。
while i < len(a) and j < len(b):
# compare and append
pass处理剩余部分
当一个列表为空时，另一个列表已经有序，因此只需将它剩余的尾部直接 append 到结果中。
out.extend(a[i:])
out.extend(b[j:])为什么尾部可以直接处理
剩余尾部已经处于有序状态，因此不需要继续比较。其中一个 extend 调用会直接添加另一个列表的全部剩余内容。
总复杂度为线性
每个元素都只会被查看一次，因此合并长度分别为 n 和 m 的两个列表需要 O(n + m) 时间。这已经是最快的复杂度。
保持稳定性
当值相等时使用 <=，可以保持相等元素的原始顺序。当您还要携带额外数据时，这种稳定性非常重要。
也可以反向合并
要在没有多余空间的缓冲区中进行合并，请改为从后端开始，并将最大元素放到最后。思路相同，只是方向相反。
从合并到排序
先拆分，再分别排序，最后合并：这种递归过程就是归并排序。您刚学会的双指针合并是它的核心引擎。
快速检查
您正在使用两个指针合并两个已排序的列表。
总结
分别用一个指针遍历两个已排序的列表，始终取较小的首元素，最后处理剩余尾部。它的复杂度为 O(n + m)，也是归并排序的基础。🚀
常见问题解答
「合并两个有序序列」课时是免费的吗？
是的 — 「合并两个有序序列」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「合并两个有序序列」这节课中我会学到什么？
各用一个指针遍历两个列表 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「合并两个有序序列」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 有序数组上的双指针
- 寻找和为给定值的一对元素
- 原地删除重复项
- 合并两个有序序列