2. 两数相加(java)

2024-01-03 16:52:25

题解博客:链表相加问题

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

解题思路:

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

具体的步骤如下:

  1. 创建一个虚拟头节点 pre 和一个指针 cur,用于构建结果链表。将 cur 初始化为 pre
  2. 初始化进位 carry 为 0。
  3. 使用循环遍历两个链表,直到其中一个链表遍历完成为止。在每一次循环中,执行以下操作:
    • 获取当前两个节点的值,如果其中一个链表已经遍历完成,则将其值设为 0。
    • 计算当前位的和 sum,为两个节点的值加上进位 carry
    • 更新进位 carry,为 sum 除以 10 的商。
    • 更新当前位的值 sum,为 sum 对 10 取余的结果。
    • 创建一个新的节点,将 sum 存储在其中,并将其连接到结果链表的末尾。
    • 将指针 cur 移动到结果链表的最后一个节点。
    • 如果链表 l1l2 还有下一个节点,则将对应指针向后移动一位。
  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,以便在递归过程中传递和处理进位信息。

文章来源:https://blog.csdn.net/weixin_61034310/article/details/135364168
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。