-
Notifications
You must be signed in to change notification settings - Fork 2
/
LinkedListTwoNumbers.java
107 lines (95 loc) · 2.76 KB
/
LinkedListTwoNumbers.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
package linked_list;
/**
* 445. Add Two Numbers II
* You are given two non-empty linked lists representing two non-negative integers.
* The most significant digit comes
* first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
*
* You may assume the two numbers do not contain any leading zero, except the number 0 itself.
*
* Follow up:
* What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
*
* Example:
*
* Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 8 -> 0 -> 7
*
* IMP-3: Common question on lists
*/
public class LinkedListTwoNumbers {
/**
* Simple solution from leetcode to add two lists together
* @param l1
* @param l2
* @return
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// find the length of both lists
int n1 = 0, n2 = 0;
ListNode curr1 = l1, curr2 = l2;
while (curr1 != null) {
curr1 = curr1.next;
++n1;
}
while (curr2 != null) {
curr2 = curr2.next;
++n2;
}
// parse both lists
// and sum the corresponding positions
// without taking carry into account
// 3->3->3 + 7->7 --> 3->10->10--> 10->10->3
curr1 = l1;
curr2 = l2;
ListNode head = null;
while (n1 > 0 && n2 > 0) {
int val = 0;
if (n1 >= n2) {
val += curr1.val;
curr1 = curr1.next;
--n1;
}
if (n1 < n2) {
val += curr2.val;
curr2 = curr2.next;
--n2;
}
// update the result: add to front
ListNode curr = new ListNode(val);
curr.next = head;
head = curr;
}
// take the carry into account
// to have all elements to be less than 10
// 10->10->3 --> 0->1->4 --> 4->1->0
curr1 = head;
head = null;
int carry = 0;
while (curr1 != null) {
// current sum and carry
int val = (curr1.val + carry) % 10;
carry = (curr1.val + carry) / 10;
// update the result: add to front
ListNode curr = new ListNode(val);
curr.next = head;
head = curr;
// move to the next elements in the list
curr1 = curr1.next;
}
// add the last carry
if (carry != 0) {
ListNode curr = new ListNode(carry);
curr.next = head;
head = curr;
}
return head;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}