LeetCode | 合并两个有序链表
371 字
2 分钟
LeetCode | 合并两个有序链表
分类：链表
题目
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]讲解
两个链表已经有序，用两个指针 l1、l2 从头比较，每次把值更小的那个节点接到结果链表的末尾，谁的节点被取走谁就往后移。
关键点：
- 用
dummy虚拟头节点串结果，最后返回dummy.next，不用单独处理头节点（和 两数相加 一样的套路）。 - 循环条件是
l1 and l2，其中一个遍历完后，剩下的那段直接整体接上：cur.next = l1 if l1 else l2，因为剩下的本来就是有序的。
复杂度
- 迭代法：
- 时间复杂度：
O(m + n) - 空间复杂度：
O(1)
- 时间复杂度：
代码
源码
from typing import Optional
class ListNode: def __init__(self, val: int = 0, next: Optional['ListNode'] = None): self.val = val self.next = next
class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() 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测试
def build_list(vals): dummy = ListNode() cur = dummy for v in vals: cur.next = ListNode(v) cur = cur.next return dummy.next
def to_list(head): res = [] while head: res.append(head.val) head = head.next return res
sol = Solution()
assert to_list(sol.mergeTwoLists(build_list([1, 2, 4]), build_list([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]assert to_list(sol.mergeTwoLists(build_list([]), build_list([]))) == []assert to_list(sol.mergeTwoLists(build_list([]), build_list([0]))) == [0]assert to_list(sol.mergeTwoLists(build_list([1]), build_list([2]))) == [1, 2]
print("PASS")参考资料
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
LeetCode | 合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/相关文章智能推荐
1
LeetCode | 两数相加
LeetCodeLeetCode 两数相加题解：模拟竖式逐位相加，dummy 虚拟头节点串联结果链表，维护 carry 进位。
2
LeetCode | 反转链表
LeetCodeLeetCode 反转链表题解：使用迭代法逐个翻转节点指向，时间复杂度 O(n)，空间复杂度 O(1)。
3
LeetCode | 相交链表
LeetCodeLeetCode 相交链表题解：使用哈希集合或长度差对齐法找到两个链表的相交起始节点。
4
LeetCode | 两数之和
LeetCodeLeetCode 两数之和题解：使用 Python 字典作为哈希表，在一次遍历中找到目标下标。
5
LeetCode | 哈希表
LeetCode整理 LeetCode 哈希表题目的核心思路：先建表，再查表。
随机文章随机推荐
评论区
--
总访问量
--
访客数
音乐
暂未播放
0:000:00
文章
66
分类
16
标签
93
总字数
477,284
运行时长
0 天
最后活动
0 天前
