目录

一、原题题目回顾（LeetCode #2）

二、逆序版思路与代码（LeetCode 原题）

三、变种手撕原题：正序存储的两数相加

四、为什么不能直接从头加？

五、解法：使用栈

---

一、原题题目回顾（LeetCode #2）

题目原文（逆序版本）：

给你两个 非空 的链表，表示两个非负整数。
它们的每位数字都是按照 逆序 的方式存储的，
并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。

示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

二、逆序版思路与代码（LeetCode 原题）

链表是 逆序存储，也就是说最低位在最前面。
我们可以从头开始同时遍历两个链表，每次加上对应位与进位，构造新节点。

该题做法不难，其实就是直接从头到尾遍历各个链表，从左到右加即可

代码实现如下

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            carry = sum / 10;
        }

        return dummy.next;
    }
}

三、变种手撕原题：正序存储的两数相加

公司题中常见变体是：

链表从 高位到低位 存储数字，返回的结果也要保持正序。

例子如下

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
解释：7243 + 564 = 7807

四、为什么不能直接从头加？

正序的链表如下：

l1: 7 -> 2 -> 4 -> 3
l2:      5 -> 6 -> 4

如果从头开始加：

• 先加高位 7 + 5 = 12，我们不知道后面是否还有进位；

• 没法在事先就决定结果链表中高位的数。

 因此必须 从尾部（低位）开始加起。

五、解法：使用栈

思路

1. 把两个链表的所有节点值压入两个栈；

2. 每次从栈顶取出一位进行相加；

3. 生成新节点并头插到结果链表；

4. 最后返回头节点。

代码实现如下

import java.util.Stack;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        ListNode head = null;
        int carry = 0;

        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            int sum = carry;
            if (!s1.isEmpty()) sum += s1.pop();
            if (!s2.isEmpty()) sum += s2.pop();

            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
            carry = sum / 10;
        }

        return head;
    }
}

✅ 逆序版 —— 从头加，carry 向后传；
✅ 正序版 —— 从尾加，用栈或递归；