-
Notifications
You must be signed in to change notification settings - Fork 10
Expand file tree
/
Copy pathSolution2.java
More file actions
80 lines (72 loc) · 2.12 KB
/
Copy pathSolution2.java
File metadata and controls
80 lines (72 loc) · 2.12 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package leetcode.all.solution1_100;
import leetcode.common.LinkedUtils;
import leetcode.common.ListNode;
/**
* 两数相加.
* https://leetcode-cn.com/problems/add-two-numbers/description/
*
* 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
* 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
*
* 示例：
* 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
* 输出：7 -> 0 -> 8
* 原因：342 + 465 = 807
*
* @author 刘壮飞
* https://github.com/zfman.
* https://blog.csdn.net/lzhuangfei.
*/
public class Solution2 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node = new ListNode(-1);//头节点
ListNode p = node;//指示执行到的位置
int plusOne = 0;//是否进位
while (l1 != null || l2 != null) {
//计算对应位和
int v1 = (l1 != null) ? l1.val : 0;
int v2 = (l2 != null) ? l2.val : 0;
int r = v1 + v2 + plusOne;
//之和大于9，减去十即为该值，并进位
if (r > 9) {
plusOne = 1;
ListNode tmp = new ListNode(r - 10);
p.next = tmp;
p = tmp;
} else {
plusOne = 0;
ListNode tmp = new ListNode(r);
p.next = tmp;
p = tmp;
}
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
//如果最后一位仍然需要进位，创建节点
if (plusOne == 1) {
p.next = new ListNode(1);
}
return node.next;
}
public static void main(String[] args) {
//你的算法必须是高效的，否则下面这个测试集是过不去的
int[] list1 = {
2,4,3,2,4,3,2,4,3,2,
4,3,2,4,3,2,4,3,2,4,
3,2,4,3,2,4,3,2,4,3,
2,4,3,2,4,3,2,4,3,2,
4,3,2,4,3,2,4,3,2,4,
3,2,4,3,2,4,3,2,4,3,9 };
int[] list2 = {
5,6,4,2,4,3,2,4,3,2,
4,3,2,4,3,2,4,3,2,4,
3,2,4,3,2,4,3,2,4,3,
2,4,3,2,4,3,2,4,3,2,
4,3,2,4,3,2,4,3,2,4,
3,2,4,3,2,4,3,9,9,9,9 };
ListNode l1 = LinkedUtils.arrayToLinkedList(list1);
ListNode l2 = LinkedUtils.arrayToLinkedList(list2);
ListNode root = new Solution2().addTwoNumbers(l1, l2);
LinkedUtils.print(root);
}
}