已知两个长度分别为m和n的升序链表若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（）A. O(n)B. O(mxn)C. O(min(m,n))D. O(max(m,n))

考查要点：本题主要考查链表合并的时间复杂度分析，特别是最坏情况下的时间复杂度计算。

解题核心思路：
合并两个升序链表为降序链表时，需逐个比较节点值，选择较大的节点添加到结果链表中。最坏情况下，需要遍历较长链表的所有节点，因此时间复杂度由较长链表的长度决定。

破题关键点：

• 比较次数：每次比较两个链表的当前节点，取较大者，直到其中一个链表遍历完毕。
• 剩余节点处理：剩余部分直接拼接，无需额外比较。
• 最坏情况：当两个链表长度相差较大时，总时间由较长链表的长度主导。

合并两个升序链表为降序链表的过程如下：

1. 初始化指针：分别指向两个链表的头节点。
2. 逐个比较节点值：每次选择较大的节点，将其添加到结果链表，并移动对应指针。
3. 处理剩余节点：当其中一个链表遍历完毕，直接将另一个链表的剩余部分拼接到结果链表末尾。

时间复杂度分析：

• 比较次数：最多需要比较 $\min(m, n)$ 次。
• 拼接剩余节点：时间复杂度为 $O(1)$（直接修改指针）。
• 总时间复杂度：$O(\min(m, n)) + O(1) = O(\min(m, n))$。

最坏情况：
若两个链表长度相差很大（例如 $m \gg n$），合并后剩余部分拼接的时间仍由较长链表的长度主导，因此最坏时间复杂度为 $O(\max(m, n))$。