每周一个小算法-两数相加
2020-11-28 本文已影响0人
小左伯爵
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
#思路,控制3个变量,total res digit ,每计算一次,l1,l2向下挪一个
l1 l2 total res digit
9 9 +0 18 8 1 total = l1.val + l2.val + digit res = total % 10 digit = total / 10
9 9 +1 19 9 1
9 +1 10 0 1
+1 1 1 0
package itbin.leetcode;
/**
* @author chenxiaogao
* @className AddTwoNumbers
* @description TODO
* @date 2020/11/27
**/
public class AddTwoNumbers {
public static void main(String[] args) {
ListNode listNode11 = new ListNode(9);
ListNode listNode12 = new ListNode(9);
ListNode listNode13 = new ListNode(9);
listNode12.next = listNode13;
listNode11.next = listNode12;
ListNode listNode21 = new ListNode(9);
ListNode listNode22 = new ListNode(9);
ListNode listNode23 = new ListNode(4);
listNode22.next = listNode23;
listNode21.next = listNode22;
ListNode listNode = addTwoNumbers2(listNode11, listNode21);
listNode.toString();
}
//暴力解法
public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
ListNode res = new ListNode();
ListNode cur = res;
int digit = 0;
while (l1 != null || l2 != null) {
int total = digit;
if (l1 != null) {
total += l1.val;
l1 = l1.next;
}
if (l2 != null) {
total += l2.val;
l2 = l2.next;
}
digit = total/10;
cur.next = new ListNode(total % 10);
cur = cur.next;
}
if (digit != 0) {
cur.next = new ListNode(digit);
}
return res.next;
}
//递归解法
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
int total = l1.val + l2.val;
int digit = total / 10;
ListNode res = new ListNode(total % 10);
if (l1.next != null || l2.next != null || digit != 0) {
l1 = l1.next == null ? new ListNode(0) : l1.next;
l2 = l2.next == null ? new ListNode(0) : l2.next;
l1.val += digit;
res.next = addTwoNumbers2(l1, l2);
}
return res;
}
}
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() {
System.out.println(val);
while (next != null) {
System.out.println(next.val);
next = next.next;
}
return null;
}
}