解题思路

1. 利用链表逆序存储的特点，从低位到高位依次相加。
2. 使用进位 (carry) 变量 来存储进位值，确保高位正确。
3. 遍历 L1 和 L2：
   • 取出 L1 和 L2 当前位的值（如果某个链表已遍历完，则补 0）。
   • 计算 sum = val1 + val2 + carry，更新 carry = sum // 10，当前位 sum % 10 作为新节点存入结果链表。
   • 继续遍历，直到 L1 和 L2 都遍历完，且 carry == 0。
4. 构建结果链表，输出时用空格分隔节点值，0 仅输出一次。

Leetcode 28.两数相加-原题链接

题目描述

给定两个非空链表 L1 和 L2，表示两个非负整数。
它们的每位数字按逆序存储，每个节点只能存储一位数字。

请计算它们的和，并以相同的逆序链表形式返回结果。

输入描述

输入包含多组测试数据。

第一行输入一个整数 T（$1 \leq T \leq 100$），表示测试用例的数量。

对于每个测试用例：

• 第一行输入一个整数 n（$1 \leq n \leq 100$），表示链表 L1 的节点数。
• 第二行输入 n 个整数（$0 \leq Node.val \leq 9$），表示 L1 的各位数字，按逆序存储。
• 第三行输入一个整数 m（$1 \leq m \leq 100$），表示链表 L2 的节点数。
• 第四行输入 m 个整数（$0 \leq Node.val \leq 9$），表示 L2 的各位数字，按逆序存储。

输出描述

对于每个测试用例，输出一行，表示两个链表相加后的结果，格式为：

• 按逆序存储的和，各位数字用空格分隔。
• 如果结果为 0，仅输出 0，不输出额外空格或换行。

样例输入

3
3
2 4 3
3
5 6 4
1
0
1
0
7
9 9 9 9 9 9 9
4
9 9 9 9

样例输出

7 0 8
0
8 9 9 9 0 0 0 1

提示

• 每个链表的长度在 [1, 100] 之间。
• 每个节点的值范围是 [0, 9]。
• 输入保证数字没有前导零（即不会出现 0 1 2 这样的情况）。