Leetcode0002.两数相加【中等】

题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：

image.png

输入：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
• 题目数据保证列表表示的数字不含前导零

解题思路

1. 创建一个新的链表，用于存储两个数相加的结果。
2. 初始化两个指针，分别指向两个链表的头部。
3. 创建一个变量carry，用于存储进位值，初始值为0。
4. 遍历两个链表，直到两个链表都遍历完。
5. 在每一位上，将两个链表对应位置的数字相加，并加上进位值carry。
6. 将相加的结果对10取余，得到当前位的值，并更新进位值carry为相加结果除以10的商。
7. 将当前位的值添加到新链表中。
8. 将两个指针向后移动一位，继续下一位的相加。
9. 如果两个链表中有一个链表已经遍历完，而另一个链表还有剩余的数字，则将剩余的数字与进位值相加，并将结果添加到新链表中。
10. 如果最后的进位值不为0，则将进位值添加到新链表的末尾。
11. 返回新链表作为结果。

题目解答

public class LeetCode0002 {
    public static void main(String[] args) {
        LeetCode0002 leetCode0002 = new LeetCode0002();
        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 res = leetCode0002.addTwoNumbers(l1, l2);
        res.print();
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int ten = 0;
        while (l1 != null || l2 != null) {
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int sum = v1 + v2 + ten;
            ten = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (ten != 0) {
            cur.next = new ListNode(ten);
        }
        return dummy.next;
    }
}

运行结果

image.png