题目难度:Medium

题目:

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本身。

示例:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)  【就是342加上465】
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

我的思路:因为要层层向下直到某一个节点的后继为空,所以想到用while循环,中间有考虑使用递归,但是发现不可以,  

  因为使用递归有两点要求:1、最内层能不依赖其他层的计算值单独计算,并且能返回一个值帮助其他层得出结果;            

              2、最外层到最内层都能层级向下表示下一层。

而本题中是LinkedList 而且是单链表,所以只有一个方向,所以由要求2可以得出,第一位(个位)既是最外层,那么问题来了,最内层(最高位)并不能自己计算而返回其他层需要的数,

相反“最外层”却可以,所以互相矛盾,不能使用递归。

明显while后面的条件应该是l1与l2任何一个不为空,

循环体内——做加法,得到值存入一个ListNode,再将这个node引用传给指针pointer的后继【pointer,作为移动的指针存储每一个值,再取自己后继传给自己】,

l1与l2取自己的后继,后续优化加上仅剩一个加数的情况(一个后续为空,进位为0)判断。代码如下:

     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int c = 0;
ListNode start = new ListNode(0); // 需要一个头结点,不然无法在第一个进行选连接
ListNode pre = start; // 需要一个前置移动节点,对每一个环节进行选择
start.next = l1;
while (l1 != null || l2 != null) {
int temp1 = 0; // 默认为0
int temp2 = 0;
if (l1 == null) {
pre.next = l2;
if (c == 0) {
return start.next; // l1为空,进位为0,后面直接就是l2
}
} else {
temp1 = l1.val; // 不为空才提取节点的值。
l1 = l1.next;
} if (l2 == null && c==0) {
return start.next; // l2为空,进位为0,后面直接就是l1
} else if (l2 != null) {
temp2 = l2.val;
l2 = l2.next;
} pre.next.val = (temp1 + temp2 + c) % 10;
c = (temp1 + temp2 + c) / 10;
pre = pre.next;
} if (c > 0) {
pre.next = new ListNode(1);
}
return start.next;
}

1562 / 1562 test cases passed. Status: Accepted Runtime: 53 ms   beats 70.37%

编写过程出现的问题:

1、在计算sum时用if else的思想去使用了三目运算符,导致长且难看。三目运算符应该用就地取值的思想,尽量不要嵌套使用

2、纠结了很久是不是该用一个ListNode来做指针。对于List中节点计算,一般都需要两个node来记录结果,一个记录最开始的位置(head),一个作为指针做计算

3、没有判断最后只剩进位的情况。当做条件判断和条件循环的时候,一定要考虑出判断和循环后是否还有什么情况是需要计算的,此题出了循环后就是l1与l2都为null,此时还有可能有进位!,所以还需要加上。

下面是参考答案:

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}

1562 / 1562 test cases passed. Status: Accepted Runtime: 63 ms   beats 33.34%

和我的思路几乎一致,并且我的算法中加入了“仅剩一个加数”的情况判断,所以性能上更优~

阿哈哈哈哈,本王终于靠自己的不世才华战胜了参考答案!

LeetCode第[2]题(Java):Add Two Numbers (链表相加)——Medium-LMLPHP 元宵快乐哈~~~~

05-07 15:56