力扣经典150题第五十七题：两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
示例
示例 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
- 题目数据保证列表表示的数字不含前导零
解题思路
本题可以通过模拟加法的方式求解，从链表的头节点开始逐位相加，注意进位的处理。具体步骤如下：
- 创建一个新的链表 dummyHead 作为结果链表的头节点，并初始化进位 carry 为 0。
- 遍历输入的两个链表 l1 和 l2，同时对应位置上的节点进行相加，如果某个链表已经遍历完成，则对应位置上的数字视为 0。
- 将两个节点值与进位相加，并更新进位。
- 将相加结果的个位数作为新节点的值，并将新节点连接到结果链表的尾部。
- 更新指针，继续遍历下一个节点，直到两个链表都遍历完毕。
- 如果最后还有进位，则在结果链表的尾部添加一个值为进位值的新节点。
- 返回结果链表的头节点。
以下是 Java 代码示例：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class AddTwoNumbers { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; } public static void main(String[] args) { AddTwoNumbers solution = new AddTwoNumbers(); // 创建示例链表 ListNode l1 = new ListNode(2); l1.next = new ListNode(4); l1.next.next = new ListNode(3); ListNode l2 = new ListNode(5); l2.next = new ListNode(6); l2.next.next = new ListNode(4); // 测试示例 ListNode result = solution.addTwoNumbers(l1, l2); while (result != null) { System.out.print(result.val + " "); result = result.next; } // 输出：7 0 8 } } 该代码通过模拟加法的方式，从链表的头节点开始逐位相加，具有时间复杂度 O(max(m, n)) 和空间复杂度 O(max(m, n)) 的特性。
