LeetCode 题解工作台
两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 示例1： 输入： l1 = [7,2,4,3], l2 = [5,6,4] 输出： [7,8,0,7] 示例2…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
手动翻转链表 `l1` 与 `l2`，将此题转换为 [2. 两数相加](https://leetcode.cn/problems/add-two-numbers/)，相加过程一致。对于最后返回的结果链表也需要进行翻转，共计三次。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0] 输出：[0]
提示：
- 链表的长度范围为
[1, 100] 0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
解题思路
方法一：翻转
手动翻转链表 l1 与 l2，将此题转换为 2. 两数相加，相加过程一致。对于最后返回的结果链表也需要进行翻转，共计三次。
# 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]:
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
dummy = ListNode()
carry = 0
while s1 or s2 or carry:
s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
carry, val = divmod(s, 10)
# node = ListNode(val, dummy.next)
# dummy.next = node
dummy.next = ListNode(val, dummy.next)
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m + n) |
| 空间 | O(m + n) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates a clear understanding of linked-list manipulation and pointer handling.
- question_mark
The candidate effectively handles edge cases such as carry and varying list lengths.
- question_mark
The candidate optimizes the solution to avoid unnecessary reversals of the lists.
常见陷阱
外企场景- error
Failing to handle the carry between nodes during the addition.
- error
Not managing the stack correctly, leading to incorrect carry calculations.
- error
Reversing the result list unnecessarily or missing the final carry node.
进阶变体
外企场景- arrow_right_alt
Add numbers represented in reverse order (least significant digit first).
- arrow_right_alt
Add numbers where digits are stored in a different order, requiring a different traversal strategy.
- arrow_right_alt
Handle larger numbers, requiring efficient use of memory and stack operations.