Leetcode 第二题 Add Two Numbers

发表于 | | 阅读次数:
字数统计: 516 | 阅读时长 ≈ 2

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

第二题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%