LeetCode | 两数相加
575 字
3 分钟
LeetCode | 两数相加
分类：链表
题目
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1]讲解
两个链表都是逆序存数字，个位对齐排在链表头部，所以可以直接从头到尾同步遍历，模拟竖式相加。
维护一个 carry 进位。每一步把两个链表当前节点的值加上进位得到 total，当前位存 total % 10，进位存 total // 10。
关键点：
ListNode(total % 10)创建一个新节点，值就是这一位的数字。cur.next = ...把新节点挂到cur后面，再cur = cur.next移到新节点，下一轮继续串。dummy是占位的空节点，不存有效数字。循环里每次挂出的节点都跟在它后面，所以最后return dummy.next就是返回结果链表的头。有了dummy，所有节点统一走cur.next = 新节点，不用单独处理头节点。- 两个链表长度可能不同，短的遍历完后按
0处理。 while条件带上carry，这样最后一位进位1也能被处理，不会丢。
复杂度
- 逐位相加：
- 时间复杂度：
O(max(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 addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy carry = 0
while l1 or l2 or carry: n1 = l1.val if l1 else 0 n2 = l2.val if l2 else 0 total = n1 + n2 + carry carry = total // 10 cur.next = ListNode(total % 10) cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next
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.addTwoNumbers(build_list([2, 4, 3]), build_list([5, 6, 4]))) == [7, 0, 8]assert to_list(sol.addTwoNumbers(build_list([0]), build_list([0]))) == [0]assert to_list(sol.addTwoNumbers(build_list([9, 9, 9, 9, 9, 9, 9]), build_list([9, 9, 9, 9]))) == [8, 9, 9, 9, 0, 0, 0, 1]assert to_list(sol.addTwoNumbers(build_list([5]), build_list([5]))) == [0, 1]
print("PASS")参考资料
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
LeetCode | 合并两个有序链表
LeetCodeLeetCode 合并两个有序链表题解：双指针遍历比较节点值，dummy 虚拟头节点串联结果链表。
2
LeetCode | 两数之和
LeetCodeLeetCode 两数之和题解：使用 Python 字典作为哈希表，在一次遍历中找到目标下标。
3
LeetCode | 反转链表
LeetCodeLeetCode 反转链表题解：使用迭代法逐个翻转节点指向，时间复杂度 O(n)，空间复杂度 O(1)。
4
LeetCode | 相交链表
LeetCodeLeetCode 相交链表题解：使用哈希集合或长度差对齐法找到两个链表的相交起始节点。
5
LeetCode | 移动零
LeetCodeLeetCode 移动零题解：使用双指针原地移动零，同时保持非零元素相对顺序。
随机文章随机推荐
评论区
--
总访问量
--
访客数
音乐
暂未播放
0:000:00
文章
66
分类
16
标签
93
总字数
477,284
运行时长
0 天
最后活动
0 天前
