LeetCode 热题100 | 21. 合并两个有序链表
大家好,今天我们来解决一道经典的算法题——合并两个有序链表。这道题在 LeetCode 上被标记为简单难度,要求我们将两个升序链表合并为一个新的升序链表。下面我将详细讲解解题思路,并附上 Python 代码实现。
题目描述
将两个升序链表合并为一个新的 升序链表 并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
解题思路
这道题的核心是合并两个有序链表。我们可以使用 双指针法 来解决这个问题。
核心思想
-
双指针法:
- 使用两个指针分别遍历两个链表。
- 比较两个指针当前节点的值,将较小的节点加入新链表。
- 移动指针,继续比较,直到其中一个链表遍历完毕。
-
处理剩余节点:
- 如果其中一个链表还有剩余节点,直接将剩余部分加入新链表。
代码实现
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeTwoLists(l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""# 创建一个虚拟头节点,简化边界条件处理dummy = ListNode()current = dummy # 当前节点指针# 遍历两个链表while l1 and l2:if l1.val <= l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# 处理剩余节点if l1:current.next = l1else:current.next = l2return dummy.next
代码解析
-
初始化:
- 创建一个虚拟头节点
dummy
,用于简化边界条件处理。 current
是当前节点指针,初始指向dummy
。
- 创建一个虚拟头节点
-
遍历链表:
- 使用
while l1 and l2
循环遍历两个链表。 - 比较
l1
和l2
当前节点的值,将较小的节点加入新链表。 - 移动
current
指针和较小的链表的指针。
- 使用
-
处理剩余节点:
- 如果
l1
或l2
还有剩余节点,直接将剩余部分加入新链表。
- 如果
-
返回结果:
- 返回
dummy.next
,即新链表的头节点。
- 返回
复杂度分析
- 时间复杂度:O(n + m),其中 n 和 m 分别是两个链表的长度。我们需要遍历两个链表的所有节点。
- 空间复杂度:O(1),只使用了常数个额外空间。
示例运行
示例 1
# 创建链表 l1 = [1,2,4]
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)# 创建链表 l2 = [1,3,4]
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)# 合并链表
result = mergeTwoLists(l1, l2)# 输出合并后的链表
while result:print(result.val, end=" -> ")result = result.next
print("None")
输出:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None
示例 2
# 创建链表 l1 = []
l1 = None# 创建链表 l2 = []
l2 = None# 合并链表
result = mergeTwoLists(l1, l2)# 输出合并后的链表
while result:print(result.val, end=" -> ")result = result.next
print("None")
输出:
None
示例 3
# 创建链表 l1 = []
l1 = None# 创建链表 l2 = [0]
l2 = ListNode(0)# 合并链表
result = mergeTwoLists(l1, l2)# 输出合并后的链表
while result:print(result.val, end=" -> ")result = result.next
print("None")
输出:
0 -> None
总结
通过双指针法,我们可以高效地合并两个有序链表。这种方法的时间复杂度为 O(n + m),空间复杂度为 O(1),能够处理较大的输入规模。希望这篇题解对你有帮助!如果还有其他问题,欢迎继续提问!
关注我,获取更多算法题解和编程技巧!