-
Notifications
You must be signed in to change notification settings - Fork 19
/
AddTwoNumbers.java
136 lines (125 loc) · 3.79 KB
/
AddTwoNumbers.java
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package oj.leetcode;
/**
* https://leetcode.com/problems/add-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
* <p>
* 数字是逆序的,所以直接遍历相加,如果不是逆序的,可以先逆序,然后采用这样的方法
* 题目似曾相识,这里是用链表,而不是数组,原理一样。
* 一次性AC
*/
public class AddTwoNumbers {
public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
ListNode prev = new ListNode(0);
ListNode head = prev;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
ListNode cur = new ListNode(0);
int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
cur.val = sum % 10;
carry = sum / 10;
prev.next = cur;
prev = cur;
l1 = (l1 == null) ? l1 : l1.next;
l2 = (l2 == null) ? l2 : l2.next;
}
return head.next;
}
/**
* AC
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
// 之和
ListNode dummy = new ListNode(-1);
dummy.next = null;
ListNode cur = dummy;
// 处理进位
int carry = 0;
ListNode p = l1, q = l2;
while (p != null && q != null) {
int sum = p.val + q.val + carry;
if (sum >= 10) {
sum = sum - 10;
carry = 1;
} else {
carry = 0;
}
ListNode node = new ListNode(sum);
node.next = cur.next;
cur.next = node;
cur = node;
p = p.next;
q = q.next;
}
while (p != null) {
int sum = p.val + carry;
if (sum >= 10) {
sum = sum - 10;
carry = 1;
} else {
carry = 0;
}
ListNode node = new ListNode(sum);
node.next = cur.next;
cur.next = node;
cur = node;
p = p.next;
}
// or
while (q != null) {
int sum = q.val + carry;
if (sum >= 10) {
sum = sum - 10;
carry = 1;
} else {
carry = 0;
}
ListNode node = new ListNode(sum);
node.next = cur.next;
cur.next = node;
cur = node;
q = q.next;
}
// 处理最后一个节点的情况
if (carry == 1) {
ListNode node = new ListNode(carry);
node.next = cur.next;
cur.next = node;
cur = node;
}
return dummy.next;
}
public static ListNode createListFromArray(int[] arr) {
ListNode head = null;
for (int i = 0; i < arr.length; i++) {
ListNode node = new ListNode(arr[i]);
node.next = head;
head = node;
}
return head;
}
public static void showList(ListNode head) {
ListNode p = head;
while (p != null) {
System.out.print(p.val + " ");
p = p.next;
}
System.out.println();
}
public static void main(String[] args) {
int arr1[] = {2, 4, 3};
int arr2[] = {5, 6, 7};
ListNode a = createListFromArray(arr1);
ListNode b = createListFromArray(arr2);
AddTwoNumbers atn = new AddTwoNumbers();
ListNode sum = atn.addTwoNumbers(a, b);
showList(sum);
}
}