在正向存储数字的链表中实现两数相加

// Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0); // head.next 默认为 null
        // ...
        // 调用 generateSumList 时，head.next (null) 被赋给 res
        head.val = generateSumList(l1.next, l2.next, head.next); 
        return head;
    }

    public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
        // ...
        // 当 l1.next 和 l2.next 都不为 null 时，会执行以下语句：
        rest = generateSumList(l1.next, l2.next, res.next); 
        // 此时 res 可能是 null，导致 res.next 触发 NullPointerException
        // ...
    }
}

/**
 * 反转单链表
 * @param head 链表头节点
 * @return 反转后的链表头节点
 */
private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next; // 暂存下一个节点
        curr.next = prev;             // 当前节点指向前一个节点
        prev = curr;                  // prev 向前移动
        curr = nextTemp;              // curr 向前移动
    }
    return prev; // prev 最终指向原链表的尾部，即反转后的头部
}

public class Solution {
    // ListNode 定义如上所示

    public ListNode addTwoNumbersForwardOrder(ListNode l1, ListNode l2) {
        // 1. 反转输入链表
        ListNode reversedL1 = reverseList(l1);
        ListNode reversedL2 = reverseList(l2);

        // 2. 相加反转后的链表（经典逆向相加问题）
        ListNode dummyHead = new ListNode(0); // 哨兵节点，简化结果链表的构建
        ListNode current = dummyHead;
        int carry = 0; // 进位

        while (reversedL1 != null || reversedL2 != null || carry != 0) {
            int val1 = (reversedL1 != null) ? reversedL1.val : 0;
            int val2 = (reversedL2 != null) ? reversedL2.val : 0;

            int sum = val1 + val2 + carry;
            carry = sum / 10; // 计算新的进位
            int digit = sum % 10; // 当前位的数字

            current.next = new ListNode(digit); // 创建新节点并连接
            current = current.next;

            if (reversedL1 != null) {
                reversedL1 = reversedL1.next;
            }
            if (reversedL2 != null) {
                reversedL2 = reversedL2.next;
            }
        }

        // 3. 反转结果链表
        return reverseList(dummyHead.next); // dummyHead.next 是逆向结果链表的头部
    }

    /**
     * 反转单链表 (同上，为完整性再次提供)
     */
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

import java.util.Stack;

public class Solution {
    // ListNode 定义如上所示

    public ListNode addTwoNumbersWithStacks(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        // 1. 将链表数字压入栈中
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        ListNode head = null; // 结果链表的头部
        int carry = 0; // 进位

        // 2. 从栈中弹出数字并相加
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int val1 = stack1.isEmpty() ? 0 : stack1.pop();
            int val2 = stack2.isEmpty() ? 0 : stack2.pop();

            int sum = val1 + val2 + carry;
            carry = sum / 10;
            int digit = sum % 10;

            // 构建结果链表：新节点总是添加到当前链表的头部
            ListNode newNode = new ListNode(digit);
            newNode.next = head; // 将新节点指向当前的头部
            head = newNode;      // 更新头部为新节点
        }

        return head;
    }
}