Day2|Day2 两数相加 Day2两数相加

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

两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0开头。
你可以按任意顺序返回答案。
【Day2|Day2 两数相加】示例 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算法

思路：

数组已经逆序摆放，就只用考虑进位及边界值问题

求新结点的值只需要考虑进位，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 ="https://www.it610.com/article/); builder.append(val); builder.append("; "); ListNode temp = next; while (temp != null) { builder.append("value ="https://www.it610.com/article/); builder.append(temp.val); builder.append("; "); temp = temp.next; } return builder.toString(); } } }

文章图片
image.png 官方解

模拟
1. 每个位置上的数直接相加，有进位时后续位置加上进位
2. 长度不一致时，短的采用补0的方式
3. 计算完还有进位，就添加新结点，值为进位
时间复杂度：O(max(m,n))，其中 m,n 为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
空间复杂度：O(max(m,n))。答案链表的长度最多为较长链表的长度 +1。