题目

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是()。

错因

A

只数了一个链表的长度，忽略了"还要把另一个链表的所有节点也走完一遍"。两个链表都要被完整扫描，复杂度不能只用 描述。

B

误以为合并 = 嵌套比较：拿 A 表的每个节点去 B 表里找位置，于是得到 。但有序链表合并是双指针线性扫描——两个指针只朝一个方向走，每个节点最多被比较一次，总比较次数 。

C

只想到"短表用完了就可以剩下长表直接拼"，于是把复杂度记成 。但短表用完后，长表剩下的部分仍然要遍历（因为是要做成降序，每个剩下的节点都得头插一次），跳不掉的步骤还是 量级。

总解析

合并的具体做法（双指针 + 头插法一次成型为降序）：

1. 设两个指针 pa pb 分别指向两表头，新链表头 head = NULL
2. 比较 pa->data 和 pb->data，取较小者摘下，头插到 head 上（头插法天然把升序输入变成降序输出）
3. 较小者的指针前进，重复
4. 一方走完后，把另一方剩下的节点逐个头插到 head 上

复杂度分析：

• 每个节点恰好被处理一次（要么在比较阶段被摘下头插，要么在收尾阶段被头插）
• 处理一个节点是
• 总操作数 = 次

所以时间复杂度是 。

为什么 ？

由 ，两者只差常数倍，渐近意义下相等。教材里两种写法都对，本题选项给的是 形式。

顺带提：升序合并成降序与升序合并成升序，复杂度量级完全相同——"降序"只是把"尾插"换成"头插"，单步代价不变。同学常把"输出方向反"误读成"复杂度变高"，没那回事。

最终答案是 D。