XingHuiSamaの宝藏之地

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

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

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

1. 算法核心思想：竖式加法模拟

题目要求对两个用链表逆序表示的数字进行求和。由于链表的头节点正好对应数字的个位，这与我们在纸上进行数学“竖式加法”从低位向高位对齐相加的过程完全一致。

核心在于维护一个进位变量（temp）。在遍历两个链表的过程中，依次将对应节点的值与进位变量相加，将结果的个位数存入新生成的链表节点中，并将十位数作为新的进位传递给下一次计算。

2. 逻辑拆解

引入虚拟头节点：由于结果需要生成一条全新的链表，使用虚拟头节点 ans 可以省去对头节点是否为空的繁琐初始化判断。
主体对齐相加：在第一个 while 循环中，两个链表同步遍历。每一步计算 pre1->val + pre2->val + temp，通过 / 10 获取进位，通过 % 10 获取当前位的值。
处理长度差异：两个数字的位数往往不同（例如 999 + 1）。当同步遍历结束后，必有一个链表已经遍历完毕。接下来的 if-else 分支将尚未遍历完的链表剩余节点与现有的进位 temp 继续相加，直到该链表也遍历结束。
最终进位处理：当两个链表均遍历结束后，进位变量 temp 可能仍不为 0（例如 5 + 5 = 10，链表遍历完后还有一个进位 1）。因此，在代码最后加上 if (temp != 0) 的判断，若有剩余进位，则再追加一个新节点，防止最高位丢失。

class 两数相加 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int temp = 0;
        ListNode* pre1 = l1;
        ListNode* pre2 = l2;

        int sum = 0;
        ListNode* result = new ListNode(0);

        ListNode* ans = result;

        while (pre1!=NULL && pre2!=NULL) {
            sum = pre1->val + pre2->val + temp;
            temp = sum / 10;
            sum = sum % 10;
            result->next = new ListNode(sum);
            result = result->next;
            pre1 = pre1->next;
            pre2 = pre2->next;
        }

        if (pre1!=NULL) {
            while (pre1!=NULL) {
                sum = pre1->val + temp;
                temp = sum / 10;
                sum = sum % 10;
                result->next = new ListNode(sum);
                result = result->next;
                pre1 = pre1->next;
            }
        }
        else if (pre2!=NULL) {
            while (pre2!=NULL) {
                sum = pre2->val + temp;
                temp = sum / 10;
                sum = sum % 10;
                result->next = new ListNode(sum);
                result = result->next;
                pre2 = pre2->next;
            }
        }

        if (temp != 0) {
            result->next = new ListNode(temp);
        }


        return ans->next;
    }
};

3. 复杂度分析

时间复杂度：O(max(M, N))。其中 M 和 N 分别为两个链表的长度。算法最多需要遍历较长链表的全部节点，操作次数与较长链表的长度呈线性关系。
空间复杂度：O(1)（仅算额外空间）。除了返回结果所需的新链表外，算法仅使用了几个整型变量和指针，占用的额外空间为常数级别。