两数相加 | 徐年の博客

力扣 2. 两数相加

题目说明

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

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

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

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

示例

示例 1：

1
2
3

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1 2	输入：l1 = [0], l2 = [0] 输出：[0]

示例 3：

1 2	输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，直接用数组将链表中的值取出来并合并让我们来看看具体如何实现的吧。

实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /*
     * 数组
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 用两个动态数组将两个链表的值取出来
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        // 取值
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                list1.add(l1.val);
                l1 = l1.next;
            }
            if (l2 != null) {
                list2.add(l2.val);
                l2 = l2.next;
            }
        }

        int size1 = list1.size();
        int size2 = list2.size();

        List<Integer> list = new ArrayList<>();
        // 进位
        int carry = 0;
        // 当前位
        int now;

        // 因为之前取链表时是逆序，所以现在顺序读取，逆序加入结果数组
        for (int i = 0; i < Math.max(size1, size2); i++) {
            now = 0;
            if (i < size1) {
                now += list1.get(i);
            }
            if (i < size2) {
                now += list2.get(i);
            }
            now += carry;
            if (now >= 10) {
                now -= 10;
                carry = 1;
            }else {
                carry = 0;
            }
            list.add(now);
        }

        // 多余的进位
        if (carry != 0) {
            list.add(carry);
        }

        ListNode result = new ListNode(list.get(0));

        ListNode temp = result;
        for (int i = 1; i < list.size(); i++) {
            temp.next = new ListNode(list.get(i));
            temp = temp.next;
        }

        return result;
    }
}