2. 两数相加(java)

题解博客：链表相加问题

题目要求我们将两个逆序存储的非负整数链表相加，并以相同的形式返回结果的链表。链表中的每个节点只能存储一位数字，因此我们需要逐位进行相加，并处理进位的情况。

解题思路：

我们可以使用两个指针 l1 和 l2 分别指向两个链表的当前节点，同时使用一个变量 carry 来记录进位。从头节点开始遍历两个链表，对于每一位数字进行相加操作，将相加结果以及进位存储在新的链表中。

具体的步骤如下：

1. 创建一个虚拟头节点 pre 和一个指针 cur，用于构建结果链表。将 cur 初始化为 pre。
2. 初始化进位 carry 为 0。
3. 使用循环遍历两个链表，直到其中一个链表遍历完成为止。在每一次循环中，执行以下操作：
   • 获取当前两个节点的值，如果其中一个链表已经遍历完成，则将其值设为 0。
   • 计算当前位的和 sum，为两个节点的值加上进位 carry。
   • 更新进位 carry，为 sum 除以 10 的商。
   • 更新当前位的值 sum，为 sum 对 10 取余的结果。
   • 创建一个新的节点，将 sum 存储在其中，并将其连接到结果链表的末尾。
   • 将指针 cur 移动到结果链表的最后一个节点。
   • 如果链表 l1 或 l2 还有下一个节点，则将对应指针向后移动一位。
4. 检查最后一位是否有进位，如果有，则将其添加到结果链表的末尾。
5. 返回结果链表的头节点 pre.next。

下面是实现该算法的 Java 代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0); // 创建虚拟头节点
        ListNode cur = pre; // 初始化结果链表指针

        int carry = 0; // 初始化进位为0
        while (l1 != null || l2 != null) {
            int x = (l1 == null) ? 0 : l1.val; // 获取l1当前节点的值，如果为空则设为0
            int y = (l2 == null) ? 0 : l2.val; // 获取l2当前节点的值，如果为空则设为0
            int sum = x + y + carry; // 计算当前位的和

            carry = sum / 10; // 更新进位
            sum = sum % 10; // 更新当前位的值
            cur.next = new ListNode(sum); // 创建新节点并连接到结果链表末尾
            cur = cur.next; // 移动结果链表指针到最后一个节点

            if (l1 != null) l1 = l1.next; // 如果l1未遍历完，则向后移动一位
            if (l2 != null) l2 = l2.next; // 如果l2未遍历完，则向后移动一位
        }
        if (carry == 1) { // 检查最后一位是否有进位
            cur.next = new ListNode(carry); // 如果有进位，则添加到结果链表末尾
        }
        return pre.next; // 返回结果链表的头节点（不包含虚拟头节点）
    }
}

另外，我们还可以使用递归的方式来解决这个问题。递归的思路与迭代类似，只是将循环替换为递归调用。递归的终止条件是当两个链表都遍历完成且没有进位时。下面是使用递归实现的代码：

class Solution {  
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
        // 递归终止条件：两个链表都为空，说明相加完毕  
        if (l1 == null && l2 == null) {  
            return null;  
        }  
          
        // 递归到下一层，处理下一位数字  
        ListNode nextNode = addTwoNumbers(l1 == null ? null : l1.next, l2 == null ? null : l2.next);  
          
        // 处理当前位数字的相加及进位  
        int x = (l1 == null) ? 0 : l1.val;  
        int y = (l2 == null) ? 0 : l2.val;  
        int sum = x + y;  
        // 如果下一节点不为空，说明有进位，需要加上进位值  
        if (nextNode != null) {  
            sum += nextNode.val / 10; // 进位值在下一节点的十位上  
            nextNode.val %= 10; // 下一节点的个位为真正的相加结果  
        }  
          
        // 判断当前位是否有进位  
        if (sum >= 10) {  
            if (nextNode == null) {  
                nextNode = new ListNode(0); // 创建新的节点来保存进位  
            }  
            nextNode.val += sum / 10; // 进位值加到下一节点上  
            sum %= 10; // 当前位的个位为真正的相加结果  
        }  
          
        // 创建当前节点并连接下一节点  
        ListNode node = new ListNode(sum);  
        node.next = nextNode;  
        return node; // 返回当前节点（包含递归调用的结果链表）  
    }  
}

注意：在实际使用时，应该调用包装函数 addTwoNumbersWrapper 来处理链表相加问题，因为它负责初始化进位为0并调用实际的递归函数 addTwoNumbers。递归函数的参数中包含了进位 carry，以便在递归过程中传递和处理进位信息。