LeetCode 21. 合并两个有序链表｜Python 解法详解

LeetCode 21. 合并两个有序链表｜Python 解法详解

CSDN 算法专题 · 链表 | 难度：简单

题目信息

• 题号：21
• 难度：简单
• LeetCode：题目链接

题目描述

将两个升序链表合并成一个新的升序链表，并返回其头节点。新链表由原链表节点拼接而成。

示例

输入：list1 = [1,2,4], list2 = [1,3,4]
输出：[1,1,2,3,4,4]

约束

两个链表节点数均不超过 50；节点值有序。

解题思路

核心观察

使用哑节点统一处理头节点。比较两个当前节点，把较小者接到结果尾部并移动对应指针；一条链表耗尽后，剩余部分本身有序，可整体接上。

推导与执行步骤

为什么这个方法正确

算法始终围绕上述核心观察维护有效状态，并且每一步只排除已经能够证明不可能产生更优答案的情况。按照执行步骤处理后，所有可能影响答案的元素或节点都会被恰好检查，因此不会遗漏合法答案；状态更新又严格遵守题目约束，所以最终结果有效。

从边界看，空区间、单个元素、全部相同或完全不匹配等情况都会落入初始化条件或循环终止条件，不需要依赖未定义状态。实现时再重点检查下标、空节点和重复元素，即可保证算法在极端输入下仍然成立。

Python 代码

# 解法核心：使用哑节点统一处理头节点。比较两个当前节点，把较小者接到结果尾部并移动对应指针；一条链表耗尽后，剩余部分本身有序，可整体接上。
# 实现步骤：
# 1. 创建 dummy 和 tail
# 2. 比较 list1 与 list2 当前值
# 3. 连接较小节点并移动指针
# 4. 连接未遍历完的剩余链表

from typing import Optional

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) –> Optional[ListNode]:
dummy = ListNode() # 哑节点用于统一处理头节点可能变化的情况
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 if list1 else list2
return dummy.next

复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)

易错点

循环结束后不要漏接剩余节点；返回 dummy.next。

总结

这道题的关键是：使用哑节点统一处理头节点。理解这一点后，再结合边界条件检查，代码就能保持清晰且稳定。