当前位置: 首页> 汽车> 时评 > 产品推广策划方案怎么做_南昌网站建设冲浪者科技_百度快速排名技术培训_微信营销方式

产品推广策划方案怎么做_南昌网站建设冲浪者科技_百度快速排名技术培训_微信营销方式

时间:2025/7/11 14:48:11来源:https://blog.csdn.net/m0_63951116/article/details/145973468 浏览次数: 0次
产品推广策划方案怎么做_南昌网站建设冲浪者科技_百度快速排名技术培训_微信营销方式

LeetCode 热题100 | 21. 合并两个有序链表

大家好,今天我们来解决一道经典的算法题——合并两个有序链表。这道题在 LeetCode 上被标记为简单难度,要求我们将两个升序链表合并为一个新的升序链表。下面我将详细讲解解题思路,并附上 Python 代码实现。


题目描述

将两个升序链表合并为一个新的 升序链表 并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

解题思路

这道题的核心是合并两个有序链表。我们可以使用 双指针法 来解决这个问题。

核心思想

  1. 双指针法

    • 使用两个指针分别遍历两个链表。
    • 比较两个指针当前节点的值,将较小的节点加入新链表。
    • 移动指针,继续比较,直到其中一个链表遍历完毕。
  2. 处理剩余节点

    • 如果其中一个链表还有剩余节点,直接将剩余部分加入新链表。

代码实现

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

代码解析

  1. 初始化

    • 创建一个虚拟头节点 dummy,用于简化边界条件处理。
    • current 是当前节点指针,初始指向 dummy
  2. 遍历链表

    • 使用 while l1 and l2 循环遍历两个链表。
    • 比较 l1l2 当前节点的值,将较小的节点加入新链表。
    • 移动 current 指针和较小的链表的指针。
  3. 处理剩余节点

    • 如果 l1l2 还有剩余节点,直接将剩余部分加入新链表。
  4. 返回结果

    • 返回 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),能够处理较大的输入规模。希望这篇题解对你有帮助!如果还有其他问题,欢迎继续提问!

关注我,获取更多算法题解和编程技巧!

关键字:产品推广策划方案怎么做_南昌网站建设冲浪者科技_百度快速排名技术培训_微信营销方式

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: