Day2 两数相加

两数相加 https://leetcode-cn.com/problems/add-two-numbers/

两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。

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

你可以按任意顺序返回答案。

示例 1：

image

输入：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]

Java算法

思路：

1. 数组已经逆序摆放，就只用考虑进位及边界值问题
2. 求新结点的值只需要考虑 进位，l1,l2,结果可以作为下一个值的参数，这样形成里递归，就使用递归处理

package sj.shimmer.algorithm;

/**
 * Created by SJ on 2021/1/26.
 */
class D2 {
    public static void main(String[] args) {
        ListNode l1 = createNode(new int[]{0});
        ListNode l2 = createNode(new int[]{0});
        System.out.println(l1.toString());
        System.out.println(l2.toString());
        System.out.println(addTwoNumbers(l1,l2).toString());
    }

    private static ListNode createNode(int[] ints) {
        ListNode node = null;
        for (int i = ints.length - 1; i >= 0; i--) {
            ListNode n = new ListNode(ints[i], node);
            node = n;
        }
        return node;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || (l1.val == 0 && l1.next == null)) {
            return l2;
        }
        if (l2 == null || (l2.val == 0 && l2.next == null)) {
            return l1;
        }
        return getNextNode(0, l1, l2);
    }

    private static ListNode getNextNode(int i, ListNode next1, ListNode next2) {
        if (i == 0) {
            if (next1 == null && next2 == null) {
                return null;
            } else if (next1 == null) {
                return next2;
            } else if (next2 == null) {
                return next1;
            }
        } else {
            if (next1 == null && next2 == null) {
                ListNode end = new ListNode();
                end.val = i;
                return end;
            }
        }

        ListNode temp = new ListNode();
        int sum;
        if (next1 == null) {
            sum = next2.val + i;
            temp.val = sum % 10;
            temp.next = getNextNode(sum / 10, null, next2.next);
        } else if (next2 == null) {
            sum = next1.val + i;
            temp.val = sum % 10;
            temp.next = getNextNode(sum / 10, next1.next, null);
        } else {
            sum = next1.val + next2.val + i;
            temp.val = sum % 10;
            temp.next = getNextNode(sum / 10, next1.next, next2.next);
        }

        return temp;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("value =");
            builder.append(val);
            builder.append("; ");
            ListNode temp = next;
            while (temp != null) {
                builder.append("value =");
                builder.append(temp.val);
                builder.append("; ");
                temp = temp.next;
            }
            return builder.toString();
        }
    }
}

image.png

官方解

1. 模拟

   1. 每个位置上的数直接相加，有进位时后续位置加上进位
   2. 长度不一致时，短的采用补0的方式
   3. 计算完还有进位，就添加新结点，值为进位

   时间复杂度：O(max(m,n))，其中 m,n 为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。

   空间复杂度：O(max(m,n))。答案链表的长度最多为较长链表的长度 +1。