LeetCode 题解工作台
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1： 输入： l1 = [2,4,3], l2 = [5,…
3
题型
13
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们同时遍历两个链表 和 ，并使用变量 表示当前是否有进位。 每次遍历时，我们取出对应链表的当前位，计算它们与进位 的和，然后更新进位的值，最后将当前位的值加入答案链表。如果两个链表都遍历完了，并且进位为 时，遍历结束。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
解题思路
方法一：模拟
我们同时遍历两个链表 和 ，并使用变量 表示当前是否有进位。
每次遍历时，我们取出对应链表的当前位，计算它们与进位 的和，然后更新进位的值，最后将当前位的值加入答案链表。如果两个链表都遍历完了，并且进位为 时，遍历结束。
最后我们返回答案链表的头节点即可。
时间复杂度 ，其中 和 分别为两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要 的时间。忽略答案的空间消耗，空间复杂度 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
carry, curr = 0, dummy
while l1 or l2 or carry:
s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry, val = divmod(s, 10)
curr.next = ListNode(val)
curr = curr.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(max(m,n)) where m and n are the lengths of the two lists, as each node is visited once. Space complexity is O(max(m,n)) for iterative solutions due to result list allocation, and O(max(m,n)) for recursive solutions due to call stack usage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check how you handle carries at each node and whether your pointers correctly traverse both lists.
- question_mark
Notice if you address unequal list lengths without skipping nodes or losing digits.
- question_mark
Consider whether your recursive or iterative approach maintains clarity and avoids unnecessary node allocations.
常见陷阱
外企场景- error
Failing to propagate carry to a new node after both lists are processed.
- error
Misaligning pointers when lists have different lengths, leading to incorrect sums.
- error
Forgetting that a null node should be treated as zero during addition, causing off-by-one errors.
进阶变体
外企场景- arrow_right_alt
Add numbers where digits are stored in forward order, requiring reversal before pointer traversal.
- arrow_right_alt
Perform addition without modifying the original lists, creating a fully new result list.
- arrow_right_alt
Implement addition using constant space by reusing existing nodes and careful pointer updates.