LeetCode 2.两数相加 java

力扣链接

2. 两数相加 - 力扣（LeetCode）

题目描述

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

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

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

解题思路

创建一个新链表记录结果，设置参数carry记录进位情况，依次遍历l1和l2的节点相加，并与carry也就是之前计算出来的进位情况进行相加计算出正确结果，carry取当前相加结果除10，为此次计算的进位情况，下次计算与其相加进行进位，每次计算对10取余加入新链表中，最后如果还有进位，则将最后的carry值直接加入结果中，最后返回新链表的头节点。

1. 初始化：

   • 创建一个头节点 Head，用于构建新的结果链表。
   • 设置一个变量 carry 初始值为0，用于记录进位。

2. 遍历链表：

   • 使用一个循环来遍历 l1 和 l2 直到两者都为空。
   • 在每一步中，获取 l1 和 l2 当前节点的值（如果它们非空），否则使用0代替。
   • 计算当前位的和 sum = carry + x + y。
   • 更新 carry 为 sum 除以10的结果，即 sum / 10。
   • 创建一个新的节点，其值为 sum % 10，并将其添加到结果链表的末尾。
   • 将当前指针移动到新创建的节点。
   • 如果 l1 或 l2 不为空，则将指针移动到下一个节点。

3. 处理最后的进位：

   • 如果在遍历结束后 carry 大于0，说明还有未处理的进位，需要再创建一个节点添加到最后。

4. 返回结果：

   • 返回结果链表的头节点，即 Head.next。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode Head = new ListNode(0); // 创建一个节点作为新链表的头结点
        ListNode current = Head; // 创建当前节点指向新链表的头节点
        int carry = 0; // 初始化进位为0
        
        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0; // 如果 l1 不为空，则取值，否则为0
            int y = (l2 != null) ? l2.val : 0; // 如果 l2 不为空，则取值，否则为0
            int sum = carry + x + y; // 计算当前位的和
            
            carry = sum / 10; // 更新进位
            current.next = new ListNode(sum % 10); // 创建新节点并添加到结果链表中
            current = current.next; // 移动到下一个节点
            
            if (l1 != null) l1 = l1.next; // 如果 l1 不为空，移动到下一个节点
            if (l2 != null) l2 = l2.next; // 如果 l2 不为空，移动到下一个节点
        }
        
        if (carry > 0) { // 如果最后还有进位，添加到结果链表中
            current.next = new ListNode(carry);
        }
        
        return Head.next; // 返回结果链表的头结点

    }
}

运行结果