LeetCode两数相加

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

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

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

这个问题是经典的“链表相加”问题。两个链表中的每个节点都存储一个数字，它们按照逆序存储，也就是说最低位数字存储在链表的头部。我们需要对链表中的数字进行逐位相加，并将结果也以链表的形式返回。

解题思路

我们可以使用逐位相加的方式来解决问题，并且需要考虑进位。

具体步骤

遍历两个链表：
- 我们从两个链表的头部开始，逐位相加两个数，同时考虑前一位的进位情况。
- 如果当前位的和大于或等于10，则产生进位。
进位处理：
- 当两个链表都遍历完后，如果还有进位，需要在结果链表的最后再加上一个节点来存储该进位。
特殊情况处理：
- 如果某个链表比另一个链表长，则在较短链表遍历完后，只需继续将长链表的剩余部分与进位相加。
返回结果链表：
- 结果链表也是按照逆序存储的形式输出。

Java代码实现

// 定义链表节点
class ListNode {int val;  // 节点的值ListNode next;  // 指向下一个节点的指针// 构造函数ListNode(int val) {this.val = val;}
}public class AddTwoNumbers {/*** 将两个链表表示的数字相加，并返回结果链表** @param l1 链表1* @param l2 链表2* @return 结果链表*/public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0); // 虚拟头节点ListNode curr = dummyHead;int carry = 0;  // 进位// 遍历两个链表while (l1 != null || l2 != null) {int x = (l1 != null) ? l1.val : 0;int y = (l2 != null) ? l2.val : 0;int sum = carry + x + y; // 当前位的和carry = sum / 10; // 更新进位curr.next = new ListNode(sum % 10); // 创建新节点存储当前位的值curr = curr.next; // 移动到下一个节点// 移动链表指针if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}// 如果最后有进位，创建新节点存储进位if (carry > 0) {curr.next = new ListNode(carry);}return dummyHead.next; // 返回结果链表的头节点}public static void main(String[] args) {// 创建链表1: 2 -> 4 -> 3 表示数字342ListNode l1 = new ListNode(2);l1.next = new ListNode(4);l1.next.next = new ListNode(3);// 创建链表2: 5 -> 6 -> 4 表示数字465ListNode l2 = new ListNode(5);l2.next = new ListNode(6);l2.next.next = new ListNode(4);// 调用addTwoNumbers方法ListNode result = addTwoNumbers(l1, l2);}
}

代码解释

ListNode 类：
- ListNode 是一个简单的链表节点类，每个节点包含一个整数 val 和一个指向下一个节点的指针 next。
addTwoNumbers 方法：
- 该方法接收两个链表 l1 和 l2，表示两个逆序存储的数字。
- dummyHead 是一个虚拟头节点，它的目的是简化链表操作（比如插入新节点），最后返回 dummyHead.next 即为结果链表的头节点。
- carry 用于存储相加时的进位。
- 使用 while 循环逐位相加 l1 和 l2，直到遍历完所有节点。
进位处理：
- 如果 carry > 0，意味着最后还有进位，需要在结果链表的尾部再加上一个节点。
示例：
- 在 main 方法中，创建了两个链表 l1 和 l2，分别表示数字 342 和 465。相加的结果为 807，对应的链表形式为 7 -> 0 -> 8。