同步遍历两链表和进位，节点值写 sum % 10，末尾保留 carry。
OJ: leetcodecn
题目 ID: add-two-numbers
难度:普及+/提高
标签:链表数学递归cpppython
日期: 2026-07-28 22:05
题意
两个逆序存储的非负整数链表，每位存一个数字，求和并以相同形式返回。
思路
同步遍历两个链表，逐位相加并处理进位。注意长度不等时补 0 处理，最后如果还有进位要新增节点。
代码
cpp
/**
* Author by Rainboy
*/
// main.cpp：同步遍历 + 进位，O(n)。
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode dummy(0), *cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
cur->next = new ListNode(sum % 10);
carry = sum / 10;
cur = cur->next;
if (l1)
l1 = l1->next;
if (l2)
l2 = l2->next;
}
return dummy.next;
}
};
ListNode *build(istream &in, int n) {
if (!n)
return nullptr;
auto head = new ListNode(0), cur = head;
for (int i = 0, v; i < n; i++) {
in >> v;
cur->next = new ListNode(v);
cur = cur->next;
}
return head->next;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
auto a = build(cin, n), b = build(cin, m);
auto head = Solution().addTwoNumbers(a, b);
for (auto p = head; p; p = p->next)
cout << p->val << ' ';
return 0;
}python
#!/usr/bin/env python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode(0)
carry = 0
while l1 or l2 or carry:
s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
cur.next = ListNode(s % 10)
carry = s // 10
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
def build(arr):
dummy = cur = ListNode(0)
for v in arr:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def main() -> None:
n, m = map(int, input().split())
a = build(list(map(int, input().split())))
b = build(list(map(int, input().split())))
head = Solution().addTwoNumbers(a, b)
while head:
print(head.val, end=" ")
head = head.next
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(max(n,m))。
- 空间复杂度：O(1)，不计结果空间。
总结
链表大数加法的关键在于统一处理"长度不同"和"末尾进位"两个边界。