题目描述
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
我的垃圾思路
- 这个题的话,根据他们提供的
ListNode类,按部就班的做下去就是可行的 - 首先逆序的数字相加,对于代码来说刚好是正序的,因为我们遍历链表时是从左往右的,刚好也是先对个位,十位,千位这样的顺序依次相加执行,所以和咱们平常的计算习惯并无太多差异
- 遍历链表时,个位与个位相加,十位与十位相加...<font color=grey size=3>(
node1[0]与node2[0]相加,node1[1]与node2[1]相加....也`就是索引相同的部分相加)</font> - 如果两个
node的当前索引都不为null,那就m=两数相加且要加上上次的进位计算,满10进1,所以当前索引保留m%10,进位m/10,若有其中一个为null,则另一个只用加进位即可 - 注意每次进入循环都要
new一个新的ListNode - 因为在代码开头已经
new了ListNode,所以最后取l3.next即为结果
我的垃圾代码
package com.dasnnj.practice.medium;
/**
* Description <p> TODO:
* 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
* <p>
* 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
* <p>
* 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
* <p>
* 示例：
* <p>
* 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
* 输出：7 -> 0 -> 8
* 原因：342 + 465 = 807
* </p>
*
* @author DASNNJ <a href="mailto:dasnnj@outlook.com"> dasnnj@outlook.com </a>
* @date 2019-05-06 09:07
*/
public class TwoAdd {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(0);
int m = 0;
//进位
int n = 0;
ListNode l = l3;
while (l1 != null || l2 != null) {
l.next = new ListNode(0);
l = l.next;
if (l1 == null) {
//则l2必然不为null
// l.val = l2.val + n;
m = l2.val + n;
} else if (l2 == null) {
//则l1必然不为null
// l.val = l1.val + n;
m = l1.val + n;
} else {
m = (l1.val + l2.val) + n;
}
n = m / 10;
if (n > 0) {
l.val = m % 10;
//此步为了最后一个位置的两个数字加了之后需要进位
l.next = new ListNode(n);
// l3.next.val = n;
} else {
l.val = m;
}
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
return l3.next;
}
public static void main(String[] args) {
ListNode l1 = new ListNode(1);
l1.next = new ListNode(8);
l1.next.next = new ListNode(3);
ListNode l2 = new ListNode(0);
l2.next = new ListNode(6);
l2.next.next = new ListNode(7);
TwoAdd t = new TwoAdd();
ListNode l3 = t.addTwoNumbers(l1, l2);
System.out.println(l3);
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("ListNode{");
sb.append("val=").append(val);
sb.append(", next=").append(next);
sb.append('}');
return sb.toString();
}
}
