Skip to content

Commit 43f5fbd

Browse files
fishercoder1534fishercoder1534
committed
add two numbers
1 parent f722358 commit 43f5fbd

File tree

1 file changed

+177
-0
lines changed

1 file changed

+177
-0
lines changed

‎MEDIUM/src/medium/AddTwoNumbers.java

Lines changed: 177 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,177 @@
1+
package medium;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
7+
import utils.CommonUtils;
8+
import classes.ListNode;
9+
10+
/**2. Add Two Numbers QuestionEditorial Solution My Submissions
11+
Total Accepted: 164672
12+
Total Submissions: 675656
13+
Difficulty: Medium
14+
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.
15+
16+
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
17+
Output: 7 -> 0 -> 8*/
18+
public class AddTwoNumbers {
19+
//Last, I went to Discuss and like this solution the best: https://discuss.leetcode.com/topic/6220/my-accepted-java-solution
20+
//it's really much more concise and elegant:
21+
//we don't actually need to collect all values from each node out and put them into a list and then do calculations
22+
//I could get out of that thinking box, I could direclty manipulate the values from the nodes and do the computation, cool!
23+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
24+
ListNode prev = new ListNode(0);
25+
ListNode head = prev;
26+
int carry = 0;
27+
while(l1 != null || l2 != null || carry != 0){
28+
ListNode curr = new ListNode(0);
29+
int sum = (l2 != null ? l2.val : 0) + (l1 != null ? l1.val : 0) + carry;
30+
curr.val = sum % 10;
31+
carry = sum / 10;
32+
prev.next = curr;
33+
prev = curr;
34+
35+
l1 = (l1 == null) ? l1 : l1.next;
36+
l2 = (l2 == null) ? l2 : l2.next;
37+
}
38+
return head.next;
39+
}
40+
41+
//then I came up with this approach: do addition digit by digit in the ArrayList, thus no matter how big the number is, it could always be computed
42+
public ListNode addTwoNumbers_ACed(ListNode l1, ListNode l2) {
43+
List<Integer> nums1 = new ArrayList();
44+
List<Integer> nums2 = new ArrayList();
45+
ListNode tmp1 = l1, tmp2 = l2;
46+
while(tmp1 != null){
47+
nums1.add(tmp1.val);
48+
tmp1 = tmp1.next;
49+
}
50+
while(tmp2 != null){
51+
nums2.add(tmp2.val);
52+
tmp2 = tmp2.next;
53+
}
54+
55+
//we don't need to reverse the two lists, just start adding them up from index 0
56+
List<Integer> shorter = (nums1.size() > nums2.size()) ? nums2 : nums1;
57+
List<Integer> longer = (shorter == nums1) ? nums2 : nums1;
58+
int[] res = new int[longer.size()+1];
59+
boolean carry = false;
60+
int i = 0;
61+
for(; i < shorter.size(); i++){
62+
int thisResult = 0;
63+
if(carry){
64+
thisResult = shorter.get(i) + longer.get(i) + 1;
65+
} else {
66+
thisResult = shorter.get(i) + longer.get(i);
67+
}
68+
if(thisResult >= 10){
69+
res[i] = Character.getNumericValue(String.valueOf(thisResult).charAt(1));
70+
carry = true;
71+
} else {
72+
res[i] = thisResult;
73+
carry = false;
74+
}
75+
}
76+
77+
if(shorter.size() == longer.size()){
78+
if(carry) res[i] = 1;
79+
}
80+
81+
for(; i < longer.size(); i++){
82+
int thisResult = 0;
83+
if(carry){
84+
thisResult = longer.get(i)+1;
85+
} else {
86+
thisResult = longer.get(i);
87+
}
88+
if(thisResult >= 10){
89+
res[i] = Character.getNumericValue(String.valueOf(thisResult).charAt(1));
90+
carry = true;
91+
} else {
92+
res[i] = thisResult;
93+
carry = false;
94+
}
95+
}
96+
if(carry) res[i] = 1;
97+
98+
CommonUtils.printArray(res);
99+
100+
ListNode pre = new ListNode(-1);
101+
ListNode next = new ListNode(-1);
102+
pre.next = next;
103+
for(int j = 0; j < res.length;){
104+
next.val = res[j];
105+
j++;
106+
if(j == res.length-1 && res[j] == 0) break;
107+
if(j < res.length)
108+
next.next = new ListNode(-1);
109+
next = next.next;
110+
}
111+
return pre.next;
112+
}
113+
114+
public static void main(String...strings){
115+
// ListNode l1 = new ListNode(2);
116+
// l1.next = new ListNode(4);
117+
// l1.next.next = new ListNode(3);
118+
// ListNode l2 = new ListNode(5);
119+
// l2.next = new ListNode(6);
120+
// l2.next.next = new ListNode(4);
121+
122+
// ListNode l1 = new ListNode(5);
123+
// ListNode l2 = new ListNode(5);
124+
125+
ListNode l1 = new ListNode(1);
126+
ListNode l2 = new ListNode(9);
127+
l2.next = new ListNode(9);
128+
129+
AddTwoNumbers test = new AddTwoNumbers();
130+
ListNode result = test.addTwoNumbers_ACed(l1, l2);
131+
CommonUtils.printList(result);
132+
}
133+
134+
//the most naive approach will result in overflow/NumberFormatException, since if the number is greater than 2^64, it won't work
135+
//sample test case: [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
136+
// [1]
137+
public ListNode addTwoNumbers_overflowed(ListNode l1, ListNode l2) {
138+
long num1 = 0, num2 = 0;
139+
List<Integer> nums1 = new ArrayList();
140+
List<Integer> nums2 = new ArrayList();
141+
ListNode tmp1 = l1, tmp2 = l2;
142+
while(tmp1 != null){
143+
nums1.add(tmp1.val);
144+
tmp1 = tmp1.next;
145+
}
146+
while(tmp2 != null){
147+
nums2.add(tmp2.val);
148+
tmp2 = tmp2.next;
149+
}
150+
StringBuilder sb = new StringBuilder();
151+
for(int i = nums1.size()-1; i >= 0; i--){
152+
sb.append(nums1.get(i));
153+
}
154+
num1 = Long.valueOf(sb.toString());
155+
sb.setLength(0);
156+
for(int i = nums2.size()-1; i >= 0; i--){
157+
sb.append(nums2.get(i));
158+
}
159+
num2 = Long.valueOf(sb.toString());
160+
long res = num1 + num2;
161+
String resStr = String.valueOf(res);
162+
sb.setLength(0);
163+
String reverse = sb.append(resStr).reverse().toString();
164+
char[] chars = reverse.toCharArray();
165+
ListNode dummy = new ListNode(-1);
166+
ListNode result = new ListNode(-1);
167+
dummy.next = result;
168+
for(int i = 0; i < chars.length; i++){
169+
result.val = Character.getNumericValue(chars[i]);
170+
if(i < chars.length-1)
171+
result.next = new ListNode(-1);
172+
result = result.next;
173+
}
174+
return dummy.next;
175+
}
176+
177+
}

0 commit comments

Comments
 (0)