链表中等1 种解法

#2两数相加

两个链表按逆序保存十进制数字，逐位相加并返回同样逆序保存的结果链表。

#链表#数学#模拟

解题主线

链表从最低位开始，遍历方向天然符合从低位到高位的加法顺序。

某条链表结束后按 0 参与计算；主循环结束后仍要处理最终进位。

解法 1：逐位模拟

同步遍历两个链表，把当前两位与 carry 相加；个位写入新节点，十位作为下一轮进位。

时间复杂度

O(max(m, n))，m、n 分别为两个链表的长度

空间复杂度

O(max(m, n))（返回链表占用；除返回值外额外空间 O(1)）

2. 两数相加 · 逐位模拟

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

同步遍历两个链表，把当前两位与 carry 相加；个位写入新节点，十位作为下一轮进位。

边界与易错点

文件名中的 twosum 容易误导：本题是第 2 题“两数相加”，不是第 1 题“两数之和”。
不要遗漏最高位进位，例如 9 + 1 应得到 0 -> 1。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q002_linkedlist_twosum.java