合并两个降序链表为一个升序链表
虾皮（Shopee）笔试编程题 · 核心代码模式
题目描述
给定两个降序链表（从头到尾值递减，如 5 → 3 → 1），请把这两个链表合并为一个新的升序链表（从头到尾值递增），并返回合并后的链表头节点。
要求复用原链表节点（不新建节点），通过调整指针完成合并。
输入格式
- 两个单链表的头节点
l1、l2； - 链表中的节点值均为整数，且链表已按降序排列；
- 链表可能为空。
输出格式
- 返回合并后升序链表的头节点。
示例
示例 1
输入：
l1: 5 -> 3 -> 1
l2: 4 -> 2
输出：
1 -> 2 -> 3 -> 4 -> 5
说明： 两条降序链表合并后整体升序。
示例 2
输入：
l1: 6 -> 4 -> 4 -> 2
l2: 5 -> 3 -> 1
输出：
1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
说明：
注意重复值 4 也被保留。
示例 3
输入：
l1: (空)
l2: 3 -> 1
输出：
1 -> 3
说明： 空链表与非空链表合并，等于把非空链表反转成升序。
解题思路
第一步：理解问题本质
标准的"合并两个有序链表"要求两条链表都是升序，但本题给的是降序链表，目标却是升序。这中间的"序"需要转换。
关键点有两个：
- 降序 → 升序 的唯一手段是反转链表；
- 归并"取较小头"的过程，等价于按序排列节点——但要注意取的比较方向。
第二步：暴力解法
思路： 把两条链表的所有节点值收集到一个数组，排序后重建一条新链表。
def MergeList(self, l1, l2):
vals = []
while l1:
vals.append(l1.val)
l1 = l1.next
while l2:
vals.append(l2.val)
l2 = l2.next
vals.sort() # 直接排序得到升序
dummy = ListNode(0)
cur = dummy
for v in vals:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
为什么不够好：
- 时间复杂度 O((n+m)·log(n+m))，排序浪费了链表已有的有序信息；
- 空间复杂度 O(n+m)，额外开辟了数组并新建了全部节点，没有"复用原节点"。
第三步：优化解法（先分别反转，再归并）
思路： 把两条降序链表分别反转成升序，然后套用经典的"两个升序链表归并"。
def MergeList(self, l1, l2):
l1 = self._reverse(l1) # 降序 -> 升序
l2 = self._reverse(l2)
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val: # 取较小头
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
特点：
- 时间复杂度 O(n+m)，思路直观，和 LeetCode 21 完全一致；
- 缺点是要反转两次链表，多一次指针遍历的开销。
第四步：最优解法（先归并成降序，最后只反转一次）
思路： 两条链表本身就是降序的。直接做归并，但这次每次取较大头，拼出来的结果依然是降序的。最后把这条降序链表整体反转一次，就得到升序。
取较大头 => 结果从头到尾递减（降序）
反转一次 => 结果从头到尾递增（升序）
为什么取较大头是正确的：
- 每条链表内部已经递减，取较大头能保证每次选中的都是"当前所有剩余节点里最大的"；
- 依次拼接，结果必然是全局降序；
- 整个流程只反转一次，比"反转两次再归并"少一次遍历。
完整代码实现
算法可视化 · 逐帧回放这道题的代码22 帧 · 录制输入 [5, 3, 1], [4, 2]
from typing import Optional
class ListNode:
def __init__(self, x=0, next=None):
self.val = x
self.next = next
class Solution:
def MergeList(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 1. 归并两条降序链表 => 一条降序链表（每次取较大头）
dummy = ListNode(0) # 哑节点：统一处理头节点，避免特判
cur = dummy # 结果链表末尾指针
while l1 and l2:
if l1.val >= l2.val: # 取较大的头节点
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 某条链表已空，另一条链表的剩余部分直接接上（仍为降序）
cur.next = l1 if l1 else l2
# 2. 整体反转 => 升序链表
return self._reverse(dummy.next)
def _reverse(self, head):
"""迭代反转链表，返回反转后的新头节点"""
prev = None
cur = head
while cur:
nxt = cur.next # 先保存后继，防止断链
cur.next = prev # 反转指针方向
prev = cur # prev 前移
cur = nxt # cur 前移
return prev
笔试环境已提供
ListNode定义，只需实现类方法；本地测试时可补定义并添加用例（见code-training/shoppee/shoppee_merge_descending_to_ascending.py）。
示例推演
以 l1: 5 -> 3 -> 1，l2: 4 -> 2 为例。
第 1 步：归并（每次取较大头）
| 轮次 | 比较（l1头 vs l2头） | 选中 | 当前结果（降序） |
|---|---|---|---|
| 1 | 5 vs 4 | 5 | 5 |
| 2 | 3 vs 4 | 4 | 5 -> 4 |
| 3 | 3 vs 2 | 3 | 5 -> 4 -> 3 |
| 4 | 1 vs 2 | 2 | 5 -> 4 -> 3 -> 2 |
| 5 | 1 vs (空) | 1 | 5 -> 4 -> 3 -> 2 -> 1 |
第 2 步：整体反转
5 -> 4 -> 3 -> 2 -> 1 （反转后）
1 -> 2 -> 3 -> 4 -> 5 （升序，正确）
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力（收集排序重建） | O((n+m)·log(n+m)) | O(n+m) | 排序浪费有序信息，且新建所有节点 |
| 先反转再归并 | O(n+m) | O(1) | 需要反转两次链表 |
| 归并后整体反转（最优） | O(n+m) | O(1) | 只反转一次，原地复用原节点 |
其中 n、m 分别为两条链表的节点数。
易错点总结
1. 归并时取错方向
题目给的是降序链表、要升序结果。如果照搬"两个升序链表归并"的 if l1.val <= l2.val，得到的是乱序结果。要先想清楚：取较大头拼出降序，再反转一次变升序，或者先反转成升序再取较小头归并。
2. 反转链表时丢链
迭代反转的经典错误是：先把 cur.next 指向 prev，再用 cur.next 继续前进，结果链表断掉。
正确顺序： 先保存后继 nxt = cur.next，再改指针、再前移。
3. 忘记处理空链表
- 两条都为空：返回空链表；
- 一条为空：把非空链表反转即可（
dummy.next = l1 if l1 else l2后整体反转已天然处理）。
4. 重复值漏掉
归并条件用 >= 或 <= 都能保留重复值，但要确保循环结束后把剩余链表的整条接上，而不是丢弃。
5. 递归反转的栈溢出
递归版 ReverseList 深度等于链表长度，长链表会栈溢出。笔试/生产环境建议用迭代版反转。
扩展思考
- LeetCode 21（合并两个升序链表）： 本题的"先反转再归并"版本与之完全等价，思路可复用。
- 头插法直接得到降序： 如果不介意重建节点，也可以"归并取较大 + 头插到结果前端"，自然形成降序，再反转一次。
- 双向链表/环形链表变体： 反转逻辑需要额外维护
prev指针，思路相同。 - 面试追问： "合并两个降序链表为一个降序链表"其实更简单——直接取较大头归并，无需反转。理解"取哪一头决定结果顺序"是这一类题的核心。
相关题目
- 21. 合并两个有序链表 — 升序归并
- 206. 反转链表 — 反转链表（迭代/递归）
- 23. 合并 K 个升序链表 — 归并的推广
- 148. 排序链表 — 链表归并排序