京公网安备11010502063487号给定两个非空链表，各自表示一个非负整数：每个结点存一位数字，而且是逆序存放的，个位在链表头。把这两个数相加，同样用逆序链表返回和。这道题的直觉写法是先把链表转成整数、相加、再拆回链表，但数字位数一多就装不下。正确的做法是像竖式加法一样从个位开始逐位相加，带着进位往后走。本文实测"先转整数"的写法在固定宽度整数上会得到什么，给出五种语言的实现，并把进位传递的过程做成分步演示。
完整题目见官方页面（链接在文末）。前几组基准用例和它们的结果由一个独立的暴力解算出（把两条链表各自转成 Python 大整数，相加，再拆回逆序数字）。一共 8 组，覆盖：长度不同、最高位有进位、进位一路传到最末、两个 0、以及 19 位以上（超出 64 位整数范围）的数：
输入 [[2,4,3],[5,6,4]] 输出 [7,0,8] 输入 [[0],[0]] 输出 [0] 输入 [[9,9,9,9,9,9,9],[9,9,9,9]] 输出 [8,9,9,9,0,0,0,1] 输入 [[5],[5]] 输出 [0,1] 输入 [[1,8],[0]] 输出 [1,8] 输入 [[9],[1,9,9,9]] 输出 [0,0,0,0,1]
按位把链表拼成整数，看起来最省事。用 Java 的 long 实现一遍，输入是一个 20 位的数（10^19，逆序存放就是 19 个 0 加一个 1）加上 9，真实输出如下：
$ javac N.java && java N # 把整条链表先转成 long 再相加的写法 a = -8446744073709551616（应该是 10000000000000000000） a + b = -8446744073709551607（应该是 10000000000000000009）
long 最大只有 9223372036854775807，10^19 装不下，回绕成了一个负数，和也就错了，而且不会有任何报错。所以这题的解法必须逐位处理，永远不把整个数装进一个整数里。Python 的整数不会溢出，所以本文的暴力解可以直接这样做，那只是用来核对答案的独立方法，不是可提交的解法。
每一轮取出两个链表当前位置的数字（某个链表已经走完就当作 0），加上上一位的进位，得到 s：这一位写入 s % 10，新的进位是 s / 10。循环条件要写成"任一链表还有结点，或者还有进位"，因为两个链表都走完之后，最后一位仍然可能产生进位，需要再补一个结点。下面是 30 个 9 加 1 的真实运行结果，进位从个位一路传到最后：
solve([9]*30, [1]) = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] （30 个 9 加 1：进位一路传到最后，长度变成 31，末尾多出一个结点 1）
Python、Java、Go、JavaScript、C++ 五种语言都是真实编译运行的。Java 和 C++ 需要自己定义 ListNode，Go 用结构体和指针，JavaScript 用类；进位的除法除了 JavaScript 需要 Math.floor（它没有整数除法），其余语言都是整数除法，Python 用 divmod 一次拿到进位和数字。
Python · 解法代码class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def add_two_numbers(l1, l2): dummy = tail = ListNode() carry = 0 while l1 or l2 or carry: # 两个链表都走完了，还要看最后有没有进位 s = carry if l1: s += l1.val l1 = l1.next if l2: s += l2.val l2 = l2.next carry, digit = divmod(s, 10) tail.next = ListNode(digit) tail = tail.next return dummy.next
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,4,3],[5,6,4]] → [7,0,8] [[0],[0]] → [0] [[9,9,9,9,9,9,9],[9,9,9,9]] → [8,9,9,9,0,0,0,1] [[5],[5]] → [0,1] [[1,8],[0]] → [1,8] [[9],[1,9,9,9]] → [0,0,0,0,1]
Java · 解法代码class ListNode { int val; ListNode next; ListNode(int v) { val = v; } } class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0), tail = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { // 走完两个链表后还要看最后的进位 int s = carry; if (l1 != null) { s += l1.val; l1 = l1.next; } if (l2 != null) { s += l2.val; l2 = l2.next; } carry = s / 10; tail.next = new ListNode(s % 10); tail = tail.next; } return dummy.next; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,4,3],[5,6,4]] → [7,0,8] [[0],[0]] → [0] [[9,9,9,9,9,9,9],[9,9,9,9]] → [8,9,9,9,0,0,0,1] [[5],[5]] → [0,1] [[1,8],[0]] → [1,8] [[9],[1,9,9,9]] → [0,0,0,0,1]
Go · 解法代码type ListNode struct { Val int Next *ListNode } func addTwoNumbers(l1, l2 *ListNode) *ListNode { dummy := &ListNode{} tail := dummy carry := 0 for l1 != nil || l2 != nil || carry != 0 { // 走完两个链表后还要看最后的进位 s := carry if l1 != nil { s += l1.Val l1 = l1.Next } if l2 != nil { s += l2.Val l2 = l2.Next } carry = s / 10 tail.Next = &ListNode{Val: s % 10} tail = tail.Next } return dummy.Next }
$ go build -o bin . && ./bin < cases.jsonl [[2,4,3],[5,6,4]] → [7,0,8] [[0],[0]] → [0] [[9,9,9,9,9,9,9],[9,9,9,9]] → [8,9,9,9,0,0,0,1] [[5],[5]] → [0,1] [[1,8],[0]] → [1,8] [[9],[1,9,9,9]] → [0,0,0,0,1]
JavaScript · 解法代码class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } } function addTwoNumbers(l1, l2) { const dummy = new ListNode(); let tail = dummy, carry = 0; while (l1 || l2 || carry) { // 走完两个链表后还要看最后的进位 let s = carry; if (l1) { s += l1.val; l1 = l1.next; } if (l2) { s += l2.val; l2 = l2.next; } carry = Math.floor(s / 10); tail.next = new ListNode(s % 10); tail = tail.next; } return dummy.next; }
$ node run.js < cases.jsonl [[2,4,3],[5,6,4]] → [7,0,8] [[0],[0]] → [0] [[9,9,9,9,9,9,9],[9,9,9,9]] → [8,9,9,9,0,0,0,1] [[5],[5]] → [0,1] [[1,8],[0]] → [1,8] [[9],[1,9,9,9]] → [0,0,0,0,1]
C++ · 解法代码struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; int carry = 0; while (l1 || l2 || carry) { // 走完两个链表后还要看最后的进位 int s = carry; if (l1) { s += l1->val; l1 = l1->next; } if (l2) { s += l2->val; l2 = l2->next; } carry = s / 10; tail->next = new ListNode(s % 10); tail = tail->next; } return dummy.next; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,4,3],[5,6,4]] → [7,0,8] [[0],[0]] → [0] [[9,9,9,9,9,9,9],[9,9,9,9]] → [8,9,9,9,0,0,0,1] [[5],[5]] → [0,1] [[1,8],[0]] → [1,8] [[9],[1,9,9,9]] → [0,0,0,0,1]
共 8 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 8/8 Java 通过 8/8 Go 通过 8/8 JavaScript 通过 8/8 C++ 通过 8/8
Python 版本另外和暴力解做了随机对拍：
随机对拍 5000 组（两个长度 1 到 12 的随机数字链表（最高位非 0），长度经常不同，进位链长短不一），solve 与 brute 的结果全部一致。
另外四种语言只在上面 8 组固定用例上验证过，其中包含长度不同、进位链、最高位进位和超出 64 位的输入，没有做大规模随机对拍。
下面的演示用 l1 = 2→4→3、l2 = 5→6→4（即 342 + 465 = 807）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示得到的结果与 solve 的返回值一致。第二位 4 + 6 + 0 = 10 时可以看到进位从 0 变成 1，并被下一位加上。