解决前向存储链表数字相加问题：策略、陷阱与高效实现

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; }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0); // 初始头节点
        // 尝试从 l1.next, l2.next 开始递归，并传递 head.next 作为结果链表的起始
        // 这里的 l1.next 和 l2.next 可能会导致跳过第一个数字
        head.val = generateSumList(l1.next, l2.next, head.next); // 错误：返回值是进位，而不是节点值
        return head; // 错误：head.val 可能被赋予一个进位，且 head.next 仍为 null
    }

    public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
        int rest, sum;

        // 处理链表长度不一致的情况，但逻辑上未能正确对齐
        if (l1.next == null && l2.next != null) {
            return generateSumList(l1, l2.next, res.next); // 错误：res.next 可能是 null
        }
        if (l1.next != null && l2.next == null) {
            return generateSumList(l1.next, l2, res.next); // 错误：res.next 可能是 null
        }

        // 递归基：当两个链表都到达末尾时
        if (l1.next == null && l2.next == null) {
            sum = l1.val + l2.val;
            if (sum > 9) {
                ListNode n = new ListNode(sum % 10, null);
                res = n; // 错误：res 是参数的局部拷贝，无法修改外部链表结构
                return 1;
            } else {
                ListNode n = new ListNode(sum, null);
                res = n; // 错误：同上
                return 0;
            }
        }

        // 递归调用
        rest = generateSumList(l1.next, l2.next, res.next); // 错误：res.next 可能是 null
        sum = l1.val + l2.val + rest;
        if (sum > 9) {
            res.val = sum % 10; // 错误：res 可能是 null
            return 1;
        } else {
            res.val = sum; // 错误：res 可能是 null
            return 0;
        }
    }
}

// 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; }
// }

class Solution {

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

    /**
     * 辅助函数：相加两个数字反向存储的链表
     * （即最低位在头部，最高位在尾部）
     * @param l1 第一个链表
     * @param l2 第二个链表
     * @return 和链表，也是反向存储的
     */
    private ListNode addTwoNumbersReversed(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // 哨兵头节点，方便处理结果链表
        ListNode current = dummyHead; // 用于构建结果链表的当前指针
        int carry = 0; // 进位

        // 当两个链表都遍历完且没有进位时，循环结束
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0; // 获取l1当前节点值，若为null则为0
            int y = (l2 != null) ? l2.val : 0; // 获取l2当前节点值，若为null则为0

            int sum = x + y + carry; // 计算当前位的和
            carry = sum / 10; // 计算新的进位
            current.next = new ListNode(sum % 10); // 创建新节点，值为当前位的数字
            current = current.next; // 移动current指针

            if (l1 != null) l1 = l1.next; // 移动l1指针
            if (l2 != null) l2 = l2.next; // 移动l2指针
        }
        return dummyHead.next; // 返回实际结果链表的头部
    }

    /**
     * 主函数：相加两个数字前向存储的链表
     * @param l1 第一个链表
     * @param l2 第二个链表
     * @return 和链表，前向存储
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 步骤1: 反转两个输入链表
        ListNode reversedL1 = reverseList(l1);
        ListNode reversedL2 = reverseList(l2);

        // 步骤2: 相加反转后的链表（现在是最低位在头部）
        ListNode sumReversed = addTwoNumbersReversed(reversedL1, reversedL2);

        // 步骤3: 反转和链表，使其恢复到前向存储的顺序
        return reverseList(sumReversed);
    }
}