Leetcode 第二题 Add Two Numbers

今天还心心念念昨天的第一题,于是上来看看第二题是个什么情况。

第二题And Two Numbers:

You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

似乎很简单嘛,两个非负的单向链表,“in reverse order”是反向的意思,那我们就把第二组数反向,243 + 465 = 708 ,终于凑出了答案,不过这样也不难嘛。。

============【以上为大误】===========

迅速不惜一切代价提交了代码,显示出错,输入[5,5] 运行结果为[1,0],而正确结果为[0,1]。:-(

他妹的怎么会是[0,1]!怎么凑也凑不成[0,1]!

于是继续读题,才明白原来根本不是链表逆转,而是加法的进制是逆着进位的:

  2   4   3
+5   6   4
          1
———————
  7   0   8

英语渣兼职不能忍呀-。-!

于是仔细分析,循环遍历每个节点,若和大于10,则用一个进位变量hex保存进位在下一次循环中加1,可以用取模(tmp % 10)和取余(tmp / 10)的方式来实现,最后一次循环若和大于10,在链表末尾添加值为1的节点。代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode firstNode = new ListNode(0);
ListNode tmpNode = firstNode;
int hex = 0;
while (l1 != null || l2 != null) {
int valOfL1 = 0;
int valOfL2 = 0;
if (l1 != null) {
valOfL1 = l1.val;
l1 = l1.next;
}
if (l2 != null) {
valOfL2 = l2.val;
l2 = l2.next;
}
int tmp = valOfL1 + valOfL2 + hex;
hex = tmp / 10;
tmpNode.next = new ListNode(tmp %10);
tmpNode = tmpNode.next;
}
if(hex == 1){
tmpNode.next = new ListNode(1);
}
return firstNode.next;
}
}

暂时还没有想到更快的办法解决这个问题,还是得滚回去翻数据结构啦。。另外对比了一下其他语言的实现,JAVA为什么会比C和C++更快呢?

0%