It is Wednesday morning in the Twin Cities of Minneapolis and St. Paul. The temperature should go up to 60F. The forecast for this Saturday calls for 80F. It seems that Saturday will be a great day for grilling some steaks. Our freezers at home are currently full with chicken and pork. The mix changes during the short summer months when we tend to favor beef. My wife suggested for us to stop by Costco in Minneapolis Saturday to see which beef cuts are available. We ill just get enough for the day.
I continue to go through a specific list of problems from LeetCode. The next one in the list is a problem I solved some time ago LeetCode 2 Add Two Numbers. You can refer to this post in my blog.
For this post I have added a second implementation.
As before, I will solve this problem using Java and the VSCode IDE on a Windows 10 computer. I will include a test scaffold because I will not use the IDE provided by LeetCode. Unless you wish to have the test code and the problem on the same source code, your best option is to solve the problem on-line using the IDE provided by LeetCode.
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Constraints: o The number of nodes in each linked list is in the range [1, 100]. o 0 <= Node.val <= 9 o It is guaranteed that the list represents a number that does not have leading zeros.
We are given tow linked lists with integer digits. We need to implement a mechanism to add the corresponding digits backwards. That should match the operations we perform when we add two integer values using pen and paper.
As usual, if interested in this problem I recommend you looking at the current description in the LeetCode web site in case something has changed.
2,4,3 5,6,4 main <<< arr1: [2, 4, 3] main <<< arr2: [5, 6, 4] main <<< l1: 2->4->3 main <<< l2: 5->6->4 main <<< l3: 7->0->8 main <<< l3: 7->0->8 0 0 main <<< arr1: [0] main <<< arr2: [0] main <<< l1: 0 main <<< l2: 0 main <<< l3: 0 main <<< l3: 0 9,9,9,9 9,9 main <<< arr1: [9, 9, 9, 9] main <<< arr2: [9, 9] main <<< l1: 9->9->9->9 main <<< l2: 9->9 main <<< l3: 8->9->0->0->1 main <<< l3: 8->9->0->0->1 9,9 9,9,9,9 main <<< arr1: [9, 9] main <<< arr2: [9, 9, 9, 9] main <<< l1: 9->9 main <<< l2: 9->9->9->9 main <<< l3: 8->9->0->0->1 main <<< l3: 8->9->0->0->1
Our test code reads the two lines of numbers which we will put in two linked lists. It seems that our test code reads the values and places them in a couple arrays. The contents of the arrays are then displayed.
As part of our test scaffold it seems that two linked lists are created and populated. The linked lists are displayed.
The first values correspond to the less significant digit of each number.
The following two lines represent the contents of the resulting linked list. You should be able to verify that the sum of the two values in linked lists 1 and 2 add up to the contents of linked list 3.
The first approach is the same as we had in the previous post with some minor cosmetic changes.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
}
This is the definition / signature of the linked list class used in this problem.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read first list of values ****
String[] strArr1 = br.readLine().trim().split(",");
// **** read second list of values ****
String[] strArr2 = br.readLine().trim().split(",");
// *** close buffered reader ****
br.close();
// **** generate array of integers for the first list ****
int[] arr1 = Arrays.stream(strArr1).mapToInt(Integer::parseInt).toArray();
// **** generate array of integers for second list ****
int[] arr2 = Arrays.stream(strArr2).mapToInt(Integer::parseInt).toArray();
// ???? ????
System.out.println("main <<< arr1: " + Arrays.toString(arr1));
System.out.println("main <<< arr2: " + Arrays.toString(arr2));
// **** generate first linked list ****
ListNode l1 = populate(arr1);
// **** generate second linked list ****
ListNode l2 = populate(arr2);
// ???? display first linked list ????
System.out.print("main <<< l1: ");
display(l1);
System.out.println();
// ???? display second linked list ????
System.out.print("main <<< l2: ");
display(l2);
System.out.println();
// **** add the two numbers and return the result as a linked list ****
ListNode l3 = addTwoNumbers0(l1, l2);
// ???? display the linked list with result ????
System.out.print("main <<< l3: ");
display(l3);
System.out.println();
// **** add the two numbers and return the result as a linked list ****
l3 = addTwoNumbers(l1, l2);
// ???? display the linked list with result ????
System.out.print("main <<< l3: ");
display(l3);
System.out.println();
}
Our test scaffold reads the data for the two linked lists creates and populates them. It then calls our solutions and displays the associated results. The second implementation was generated for this post.
/**
* Populate linked list with the specified array values.
*
* !!! NOT PART OF SOLUTION !!!
*/
static ListNode populate(int[] arr) {
// **** sanity ckeck(s) ****
if (arr.length == 0)
return null;
// **** initialization ****
ListNode h = null;
// **** traverse array adding nodes to the linked list ****
for (int i = arr.length - 1; i >= 0; i--) {
h = new ListNode(arr[i], h);
}
// **** return head of linked list ****
return h;
}
This method was used to populate a linked list with the contents of an array. This code IS NOT PART OF THE SOLUTION.
/**
* Display linked list.
*
* !!! NOT PART OF SOLUTION !!!
*/
static void display(ListNode head) {
// **** sanity check(s) ****
if (head == null)
return;
// **** traverse the link list ****
for (ListNode p = head; p != null; p = p.next) {
System.out.print(p.val);
if (p.next != null)
System.out.print("->");
}
}
This method was used to display the contents of a linked list. This code IS NOT PART OF THE SOLUTION.
/**
* Add the two numbers and return the sum as a linked list.
*
* Runtime: 2 ms, faster than 79.87% of Java online submissions.
* Memory Usage: 39.8 MB, less than 9.03% of Java online submissions.
*/
static ListNode addTwoNumbers0(ListNode l1, ListNode l2) {
// **** initialization ****
ListNode l3 = null;
ListNode p = l1;
ListNode q = l2;
int carry = 0;
ListNode tail = null;
// **** traverse the linked lists computing the sum digit by digit O(n) ****
while (p != null || q != null) {
// **** sum carry and digits for current position ****
int s = carry;
if (p != null)
s += p.val;
if (q != null)
s += q.val;
// **** update carry ****
if (s >= 10)
carry = 1;
else
carry = 0;
// **** update s ****
s %= 10;
// **** save digit in new node and append to result list ****
if (l3 == null) {
l3 = new ListNode(s);
tail = l3;
} else {
ListNode d = new ListNode(s);
tail.next = d;
tail = d;
}
// **** update p & q ****
if (p != null)
p = p.next;
if (q != null)
q = q.next;
}
// **** take care of carry bit (if needed) ****
if (carry != 0) {
ListNode d = new ListNode(carry);
tail.next = d;
tail = d;
}
// **** return sum ****
return l3;
}
This is the same implementation generated in the previous post. If interested in my comments I would like to refer you to the previous post.
/**
* Add the two numbers and return the sum as a linked list.
*
* Runtime: 2 ms, faster than 76.89% of Java online submissions.
* Memory Usage: 38.8 MB, less than 95.20% of Java online submissions.
*/
static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// **** initialization ****
ListNode l3 = null;
ListNode p = l1;
int carry = 0;
// **** traverse the linked lists computing the sum digit by digit O(n) ****
while (l1 != null || l2 != null) {
// **** add two digits (if needed) ****
if (l1 != null && l2 != null) {
// **** add two digits and carry ****
int sum = l1.val + l2.val + carry;
// **** update sum and carry ****
if (sum > 9) {
carry = sum / 10;
sum %= 10;
} else {
carry = 0;
}
// **** insert new node into l3 ****
if (l3 == null) {
p = new ListNode(sum, null);
l3 = p;
} else {
p.next = new ListNode(sum, null);
p = p.next;
}
// **** move both pointers forward ****
l1 = l1.next;
l2 = l2.next;
} else if (l1 != null) {
// **** add digit and carry ****
int sum = l1.val + carry;
// **** update sum and carry ****
if (sum > 9) {
carry = sum / 10;
sum %= 10;
} else {
carry = 0;
}
// **** insert new node into l3 ****
if (l3 == null) {
p = new ListNode(sum, null);
l3 = p;
} else {
p.next = new ListNode(sum, null);
p = p.next;
}
// **** move l1 forward ****
l1 = l1.next;
} else if (l2 != null) {
// **** add digit and carry ****
int sum = l2.val + carry;
// **** update sum and carry ****
if (sum > 9) {
carry = sum / 10;
sum %= 10;
} else {
carry = 0;
}
// **** insert new node into l3 ****
if (l3 == null) {
p = new ListNode(sum, null);
l3 = p;
} else {
p.next = new ListNode(sum, null);
p = p.next;
}
// **** move l2 forward ****
l2 = l2.next;
}
}
// **** insert new carry node into l3 ****
if (carry > 0)
p.next = new ListNode(carry, null);
// **** return sum ****
return l3;
}
We start by performing an initialization step. L3 is the linked list in which we will return our result of adding the two numbers from the two input linked lists. P represents the last element in the l3 linked list. Perhaps we should have labeled it tail. Finally, carry represents the carry value from adding two corresponding digits. Since the numbers are in decimal, and we are adding two digits at a time, the carry can be 0 or 1.
We typically add from right to left. In this case we will add from left to right while traversing both linked lists.
The “while loop” is used to traverse the linked lists from left to right. We continue looping while one of the linked lists has a digit to add.
We check for one of three conditions. The first holds when we have two digits to add, the second when we only have a digit from the first linked list and the third condition takes care of the first list empty but the second list still holding a digit. This makes sense when we add two integer values using a pen and paper.
On the first condition we add two values plus the carry which we initialize to 0. If the sum is greater than 9 we will have a carry so we need to update the sum.
The next step is to allocate an element for the third linked list. This element will hold the sum (minus the carry if needed). The new node will be inserted at the head or at the tail of l3.
We now should move forward the pointers in the lists to get ready to process the next iteration.
If you compare the second condition in which we only have a digit in l1, the set of operations match the one on the first condition but in this case we only deal with the new digit and the carry.
Please look at the code and make sure you can follow.
The third and final condition is similar to the second one. The difference is that we are dealing with the value coming from l2 instead of l1.
The addition, sum update and node creation and insertion are quite similar. Please look at the code and make sure you can follow it.
The different is that when done we only move forward on l2 because we know that l1 has no associated digit.
We are almost done. After we exit the while loop we might have a carry of 1 to take care off. We do so with the test, allocating a node for l3 with the value of the carry and inserting it at the tail of l3.
We now return l3.
The execution time of the two methods is similar. This second implementation seems to be somewhat wordier that the first, but the logic is much simpler to follow.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John