In this post we will solve the LeetCode 445 Add Two Numbers II problem using the Java programming language. We will generate two implementations of the function in question. The first will use two stacks while the second will reverse the singly linked list. When reversing linked lists we will implement an iterative and a recursive set of functions.
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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. Follow up: o Could you solve it without reversing the input lists? Related Topics: o Linked List o Math o Stack
We are given two singly linked lists with digits representing two non-negative numbers. We need to return their sum in a singly linked list. If interested in this problem I suggest you visit LeetCode and get the current version of the problem. Sometimes the requirements are updated.
We will solve this problem using the VSCode IDE on a Windows computer. Since Java is quite portable you could use the platform of your choice. That said; the simplest way to solve a problem is to use the online IDE provided by LeetCode. I will not use it due to the fact that I like to keep the solution with the test cases together.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
The signature for the function of interest matches the requirements. We are provided two linked lists and our result must be packaged on a linked list.
Since I will be solving the problem on my computer, I will need to generate a test scaffold which will read the values for the two linked lists, will generate the linked lists, will invoke the function of interest and finally will display the resulting linked list. Please note that the test code IS NOT PART OF THE SOLUTION! Just go ahead and solve the problem using the online IDE provided by LeetCode.
7,2,4,3 5,6,4 main <<< arr1: [7, 2, 4, 3] main <<< arr2: [5, 6, 4] main <<< l1: 7,2,4,3 main <<< l2: 5,6,4 main <<< output: 7,8,0,7 main <<< output: 7,8,0,7 1,2,3 4,5,6 main <<< arr1: [1, 2, 3] main <<< arr2: [4, 5, 6] main <<< l1: 1,2,3 main <<< l2: 4,5,6 main <<< output: 5,7,9 main <<< output: 5,7,9 9,2,3 9,5,6 main <<< arr1: [9, 2, 3] main <<< arr2: [9, 5, 6] main <<< l1: 9,2,3 main <<< l2: 9,5,6 main <<< output: 1,8,7,9 main <<< output: 1,8,7,9 9,9 9,9 main <<< arr1: [9, 9] main <<< l1: 9,9 main <<< l2: 9,9 main <<< output: 1,9,8 0 0 main <<< arr1: [0] main <<< l1: 0 main <<< l2: 0 main <<< output: 0 0 1,2,3,4 main <<< arr1: [0] main <<< arr2: [1, 2, 3, 4] main <<< l1: 0 main <<< l2: 1,2,3,4 main <<< output: 1,2,3,4 main <<< output: 1,2,3,4 3,9,9,9,9,9,9,9,9,9 7 main <<< arr1: [3, 9, 9, 9, 9, 9, 9, 9, 9, 9] main <<< arr2: [7] main <<< l1: 3,9,9,9,9,9,9,9,9,9 main <<< l2: 7 main <<< output: 4,0,0,0,0,0,0,0,0,6 main <<< output: 4,0,0,0,0,0,0,0,0,6 1 9,9 main <<< arr1: [1] main <<< arr2: [9, 9] main <<< l1: 1 main <<< l2: 9,9 main <<< output: 1,0,0 main <<< output: 1,0,0
Each test case is separated from others by two blank lines.
The first two lines in a test case hold the values that we will use to generate the linked lists. Our test scaffold displays the contents of the first array of values. Apparently while cleaning up the code I deleted displaying the second array. Sorry about that. I will correct the code in the GitHub repository (done).
The test code then creates, populates and displays the two linked lists that will be used as arguments for the function of interest. Note that I like to display values as I develop software in order to make sure that a mistake is not carried forward and causes a problem later in the code which in general tends to be harder to debug. I like to use a Test Driven Development approach.
Finally our test code calls the function of interest and displays the returned linked list holding the sum of numbers. We have a single output because only one implementation is called at a time. I missed calling the second implementation. Since the first implementation does not disturb the input arguments (linked lists) I will call both implementations of the function of interest in the version I place in GitHub (done).
/**
* Test scaffold.
*
* !!! NOT PART OF SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read node values for l1 ****
int[] arr1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read node values for l2 ****
int[] arr2 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** ****
br.close();
// ???? ????
System.out.println("main <<< arr1: " + Arrays.toString(arr1));
System.out.println("main <<< arr2: " + Arrays.toString(arr2));
// **** initialization ****
ListNode l1 = null;
ListNode l2 = null;
ListNode sum = null;
ListNode tail = null;
// **** populate l1 ****
for (int val : arr1) {
// **** create new node ****
ListNode n = new ListNode(val);
// **** add node to linked list ****
if (l1 == null) {
l1 = n;
tail = n;
} else {
tail.next = n;
tail = n;
}
}
// ???? ????
System.out.println("main <<< l1: " + dump(l1));
// **** populate l2 ****
for (int val : arr2) {
// **** create new node ****
ListNode n = new ListNode(val);
// **** add node to linked list ****
if (l2 == null) {
l2 = n;
tail = n;
} else {
tail.next = n;
tail = n;
}
}
// ???? ????
System.out.println("main <<< l2: " + dump(l2));
// **** call the function of interest ****
sum = addTwoNumbers0(l1, l2);
// **** display output ****
System.out.println("main <<< output: " + dump(sum));
// **** call the function of interest ****
sum = addTwoNumbers(l1, l2);
// **** display output ****
System.out.println("main <<< output: " + dump(sum));
}
The test scaffold is slightly more complicated than in other posts in this blog.
It starts by reading the input data from the first two lines in the current test case. An int[] array is created and populated for each linked list. The contents of the two arrays are then displayed to verify that all is well so far.
A set of variables are declared. The first two are associated with the two linked lists which will serve as arguments to the function of interest. The `sum` is associated with the output linked list. It should contain the integers for the result of the addition. The `tail` is used to track the tail while populating the `l1` and `l2` linked lists.
The code then populates the two linked lists that will be used as arguments to the function of interest. The contents of both linked lists are displayed for us to verify that all is well so far. Please note that we are always using a Test Driven Development approach when developing all the code in this and all posts in this blog.
The test code then calls the first implementation of the function of interest and display the result. It repeats the steps with the second implementation.
We will use two different approaches to solve the solution. In the first one we will use a couple stacks. In the second we will reverse the linked lists in order to avoid using the extra space.
/*
* Definition for singly-linked list.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int x) { val = x; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
@Override
public String toString() {
return "" + this.val;
}
}
Since we are developing the code on my computer I will have to implement the ListNode class. Of course if you are using the online IDE provided by LeetCode, you will not have to implement this class. Such implementation IS NOT PART OF THE SOLUTION!
/**
* Add the two numbers and return the sum as a linked list.
*
* Using 2 stacks.
*
* 1563 / 1563 test cases passed.
* Status: Accepted
* Runtime: 3 ms
* Memory Usage: 39.4 MB
*/
static public ListNode addTwoNumbers0(ListNode l1, ListNode l2) {
// **** sanity check(s) ****
if (l1.val == 0 && l2.val == 0) return new ListNode(0);
// **** initialization ****
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
ListNode ll = null;
int carry = 0;
// **** push l1 into s1 - O(n) ****
for (ListNode p = l1; p != null; p = p.next)
s1.push(p.val);
// **** push l2 into s2 - O(n) ****
for (ListNode p = l2; p != null; p = p.next)
s2.push(p.val);
// **** loop adding ditigs from the stacks and populating linked list - O(n) ****
while (!s1.isEmpty() || !s2.isEmpty()) {
// **** compute sum ****
int sum = carry;
if (!s1.isEmpty()) sum += s1.pop();
if (!s2.isEmpty()) sum += s2.pop();
// **** add digit to linked list ****
ll = new ListNode(sum % 10, ll);
// **** update carry ****
carry = sum / 10;
}
// **** take care of carry - O(1) ****
if (carry != 0) ll = new ListNode(carry, ll);
// **** return linked list sum ****
return ll;
}
We start by performing some sanity checks.
We then create the necessary variables. We will use two stacks to access the digits in order for the sum. The digits will be in reversed order as they are in the linked lists. This is how most (never say all) people perform the addition operation. The `ll` linked list will hold the digits for the sum. The `carry` represents the digit (in this case 0 or 1) that is generated when two digits are added.
We then push into the two stacks the digits from the respective linked lists. Please note that during development I had two statements that displayed the contents of the stacks. I removed them after I checked that all was working fine at this point.
We then have a loop that will continue as long as one of the two stacks has a digit. This takes into account if either linked list contains more digits than the other.
In the loop we perform the addition of the carry, a digit from the first linked list (if any) and the corresponding digit (if any) from the second linked list. At this point we are not using the linked list but the stacks which hold the digits in the proper order.
We add to the `ll` linked list the digit in the `sum` and update the `carry`. Please note that the value in the `carry` may be 0 or 1.
When we run out of digits in both stacks, we need to take into consideration the value of the `carry`. This is illustrated in several of the test cases and in particular when we add 99 + 1.
When all is said and done we return the linked list `ll` holding the result of the addition operation.
Please take a look at the comments section in this function. It illustrates the time and space it took. In this case execution is O(n) and space is O(n).
/**
* Add the two numbers and return the sum as a linked list.
*
* 1563 / 1563 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 39.6 MB
*/
static public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// **** sanity check(s) ****
if (l1.val == 0 && l2.val == 0) return new ListNode(0);
// **** initialization ****
ListNode ll = null;
int carry = 0;
// **** reverse l1 - O(n) ****
l1 = reverse(l1);
// **** reverse l2 - O(n) ****
l2 = reverseList(l2);
// **** traverse both lists - O(n)****
while (l1 != null || l2 != null) {
// **** for ease of use ****
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;
// **** sum carry and digits ****
int sum = carry + a + b;
// **** add digit to linked list ****
ll = new ListNode(sum % 10, ll);
// **** compute carry ****
carry = sum / 10;
// **** update list references ****
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
// **** add carry to linked list (if needed) ****
if (carry != 0) ll = new ListNode(carry, ll);
// **** return sum linked list ****
return ll;
}
In this implementation we will reverse the order of the digits in the two input linked lists.
We start by performing some sanity checks and initialization.
We reverse the order of the digits in `l1` using the reverse() function. We will see the implementation of this function shortly. We then reverse the contents of `l2` but we use a different auxiliary function that achieves the same result. Will see this implementation shortly.
Once again, as I was developing this code, I displayed the contents of both lists after they were reversed. This way we can proceed knowing that all is well so far (TDD approach).
We enter a loop that processes the contents of both lists. The loop terminates when both linked lists are empty.
For ease of use we assign the values of the next two digits from the respective linked lists. Note that if one of the lists does not contribute a digit, we assign the associated variable `a` or `b` a value of 0.
The sum is then computed taking into account the `carry` which we initialized to 0.
In a similar fashion as we did in the previous implementation of the function of interest, we create and populate a new element for the `ll` linked list and update the value of the `carry`.
The pointers (references) are then updated to move to the next set of integers (it could be a single digit).
When the loop terminates, as in the previous implementation, we need to take care of the `carry`.
At this point we are done and need to return the `ll` linked list as the result.
/**
* Reverse linked list.
* Iterative call.
* Auxiliary function.
*/
private static ListNode reverse(ListNode ll) {
// **** sanity check(s) ****
if (ll.next == null) return ll;
// **** initialization ****
ListNode next = null;
ListNode prev = null;
ListNode curr = ll;
// **** traverse the linked list - O(n) ****
while (curr != null) {
// **** point to next node in the list ****
next = curr.next;
// **** point to previous node in the list ****
curr.next = prev;
// **** update previous ****
prev = curr;
// **** move to the next node in the list ****
curr = next;
}
// **** new head of linked list ****
return ll = prev;
}
This function is used to reverse the contents of the linked list. The approach used is iterative.
We start by performing a sanity check. If the linked list contains a single element, there is no need to reverse the linked list.
We then declare and initialize three variables.
We then enter a while loop that ends when all the nodes in the linked list have been traversed.
The four steps are very well defined. The article Reverse a linked list by GeeksforGeeks provides an animation that shows how the three variables are used to reverse the linked list.
Note that at each iteration the idea is to be able to change the next reference form pointing to the head of the original linked list to the previous element.
After the loop completes, we need to change the head of the linked list to point to the node at the end of the original list. Such an element is pointed to by the `prev` variable.
/**
* Reverse linked list.
* Recursive call entry point.
*/
static public ListNode reverseList(ListNode ll) {
// **** sanity check(s) ****
if (ll.next == null) return ll;
// **** reverse the linked list ****
return reverseList(ll, ll, new ListNode[1]);
}
This auxiliary method reversed the linked list using a recursive approach. I just wanted to implement such an algorithm using a Test Driven Development approach.
I started by implementing the code using global variables. After the recursive function was completed, I switched the global variables to arguments and an initialization function which we are looking at now.
We start the auxiliary function by performing a sanity check. This is the same check we did for the iterative implementation.
We then call a recursive function with three arguments. The first is the current node in the list, which at this point is `ll`. We pass `ll` as the old head or `ll`. We will use this value to set the `next` reference in the last node in the reversed list. The last argument `rh` represents the head of the reversed list. This will be used to return the head of the reversed linked list.
/**
* Reverse linked list.
* Recursive call.
*/
private static ListNode reverseList(ListNode ll, ListNode oh, ListNode[] rh) {
// **** end condition (set the head for the reversed linked list) ****
if (ll.next == null) {
rh[0] = ll;
}
// **** recurse ****
else {
// **** recursive call ****
reverseList(ll.next, oh, rh);
// **** update next on previous node ****
ll.next.next = ll;
// **** set next on current node && return reversed head ****
if (ll == oh) {
ll.next = null;
return rh[0];
}
}
// **** return linked list ****
return ll;
}
We start by defining the end condition. This is achieved when the last node points to `null`.
The recursive condition makes a recursive call using the next node in the linked list.
After we have traversed the linked list, the recursive calls start returning. We then update the `next` reference in the previous node. You can observe this by single stepping with the IDE or adding a `println` call.
When we visit the original tail node, we need to set the `next` value to null and return the reversed head contained in the `rh` variable.
Note that the steps are similar to the ones we took in the reverse() function.
Specifying the different steps I took to get this function to work is long and complicated when using a post. I believe that a YouTube video would do a better job. In a couple days I will be working on starting a YouTube channel associated with this blog. At that time I will be considering implementing all solutions in Java and C++.
/**
* Dump contents of linked list.
*
* !!! NOT PART OF SOLUTION !!!
*/
private static String dump(ListNode ll) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** populate string builder ****
for (ListNode p = ll; p != null; p = p.next) {
sb.append(p.val);
if (p.next != null)
sb.append(",");
}
// **** return string ****
return sb.toString();
}
This function is used by the main() function (our test scaffold) to display the contents of a linked list.
We initialize a string builder. We then enter a loop that traverses the linked list. After appending the value of the current node to the string builder, we append a separator if the node is not the tail. When all is said and done we return the string value of the string builder. {Please note that this function IS NOT PART OF THE SOLUTION!
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named AddTwoNumbersII.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
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 / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John