Hope your day is going well. I have not checked the mail box in a few days. I will have to do so by the end of the workday. In this day and age of on-line communications it seems that due to security and privacy companies continue to send information and documents via USPS.
I was looking at a LeetCode problem to solve next when I found LeetCode 2. Add Two Numbers. The title for the problem and the description sounded quite similar to the problem Add Strings which we solved a day or so ago. I decided to give it a try. Hopefully we will use some of the same techniques we used to solve the last one.
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.
The digits for the two numbers we need to add are provided in two linked lists. It seems we are provided with two non-integer numbers. Last time the input data was provided in two strings. Since we have done something similar in this week, we should be ready to look at the samples provided by LeetCode.
Note as in the past problem, I will generate a solution on my computer. I will use the Java programming language on a Windows 10 machine using the VSCode IDE. You can follow suit or use the IDE provided by LeetCode. In my case, I will implement the solution and test it. Once I feel confident will copy the associated code into LeetCode and run it.
2,4,3 5,6,4 main <<< arr1: [2, 4, 3] main <<< arr2: [5, 6, 4] main <<< ll1: 2->4->3 main <<< ll2: 5->6->4 main <<< ll3: 7->0->8 0 0 main <<< arr1: [0] main <<< arr2: [0] main <<< ll1: 0 main <<< ll2: 0 main <<< ll3: 0 9,9,9,9,9,9,9 9,9,9,9 main <<< arr1: [9, 9, 9, 9, 9, 9, 9] main <<< arr2: [9, 9, 9, 9] main <<< ll1: 9->9->9->9->9->9->9 main <<< ll2: 9->9->9->9 main <<< ll3: 8->9->9->9->0->0->0->1
Our test scaffolding seems to read the two input lines. After that the test code should be converting the strings into integer arrays. The content of the arrays seem to be displayed. The digits seem to match. All is well so far.
Then the test code seems to create linked lists for the two operands. The linked lists are displayed.
Finally our test code seems to generate the result and display it. The three results seem to match the input values. Looks good. Let’s take a look at the signature for the function we need to implement.
/**
* 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) {
}
}
The class description used for the ListNode is provided. In my case I will have to implement the class since I will be generating the solution on my computer.
The signature seems to match the description of the problem. We will need to generate the linked lists so we can pass them to the function / method we will be using to implement the solution.
/**
* 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 ll1 = populate(arr1);
// **** generate second linked list ****
ListNode ll2 = populate(arr2);
// ???? display first linked list ????
System.out.print("main <<< ll1: ");
display(ll1);
System.out.println();
// ???? display second linked list ????
System.out.print("main <<< ll2: ");
display(ll2);
System.out.println();
// **** add the two numbers and return the result as a linked list ****
ListNode ll3 = addTwoNumbers(ll1, ll2);
// ???? display the linked list with result ????
System.out.print("main <<< ll3: ");
display(ll3);
System.out.println();
}
As expected we read the two lines providing the list of digits for the numbers we will be adding. We split the digits into strings. We use the strings to generate integer arrays with the values. We then call a function to generate each linked list. We display the linked lists to make sure all is well so far. We the call the function we need to generate as our solution. The results are displayed. Our test scaffolding which IS NOT PART OF THE SOLUTION seems to match the output and the results for the three sample tests provided by LeetCode.
/**
* 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 is the function we developed to populate the linked list with an array of integers.
/**
* 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 function is used to traverse and display the contents of a linked list. We use it to make sure the contents of the linked lists are satisfactory to us as we work implementing our 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.2 MB, less than 78.62% of Java online submissions.
*/
static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// **** initialization ****
ListNode ll3 = 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 (ll3 == null) {
ll3 = new ListNode(s);
tail = ll3;
} 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 ll3;
}
This is the implementation of our solution. Recall that the digits we need to add are provided in the linked lists from lowest to highest positions.
We initialize a set of variables. The result of our sum will be placed in the ll3 linked list which we will returned to the caller when done.
The main loop is used to traverse the digits in the proper order. In our case we will traverse the linked list in order. Note we stop when both pointers are null.
Once in the loop we generate the sum of the carry, the digit in the first linked list (if available) and the digit of the second linked list (if available). Recall the first or second operand may have more, less or same number of digits.
We then compute / update the carry. We adjust the sum so we only have a single digit.
We save the digit in a new node and append it to the third linked list.
The last thing we need to do is update the p and q pointers.
One we are done with all the digits in both linked lists we exit the loop. We need to check is we have a carry. If so we need to append it to the result linked list.
We then returned the linked list with the result.
Definitely we were able to use concepts and techniques we developed / learned in the previous post referred earlier.
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, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,050 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
Regards;
John
john.canessa@gmail.com