Introductory and "Add Two Numbers"

Hello everyone,

Welcome to my new blog! I am starting this blog to be a personal portfolio of things relating to CS: personal projects, information on different data structures and algorithms, LeetCode problems, and more!

Today, I will be going through a LeetCode problem called "Add Two Numbers." I started another blog for a CS class I was taking, but I am still relatively new to blogging so most posts may not flow that well. For these LeetCode problem posts, I will include a link to my solution it at the end of the post. Without further ado, lets get right into it!

Add Two Number

"Add Two Numbers" is a medium difficulty LeetCode problem. The prompt states the following:

We need a implement the addTwoNumbers(ListNode* l1, ListNode* l2) to add two numbers, represented by linked lists, and return the sum, also represented by a linked list. From the prompt, we know a few things:

1. The given linked lists contain at least one number.
2. The number represented in the linked list are non-negative (unsigned)
3. The digits are in reverse order.

What we do not know are the maximum length of the linked lists and if the linked lists have the same size.

Possible Solutions

I came up with two possible solutions to the problem:

1. Turn the linked lists into strings, then turn the strings into integers to conduct addition. After doing the addition, turn the sum integer into a string and then into our "result" linked list and return it.
2. Add the numbers directly using the given linked lists.

I first started with Solution #1 because I wanted to avoid interacting with the linked lists as much as possible. It also allows me to ignore the size of the linked lists, as the linked lists will become integers before the addition. However, there is a lot of conversions.

However, Solution #1 does not work because some of the numbers that the linked lists represent require more than 8 bytes to be stores, and 8 bytes is the size of an int. I discovered this after I got an std::out_of_range exception when I was using std::stoul() to convert my strings into an unsigned long.

I ended up having to implement Solution #2. However, it was tricky to implement:

1. I can get two linked lists of unequal length.
2. When adding two numbers I get a sum that is greater than or equal to 10.
3. The linked lists I had to use in the implementation are created through a struct called ListNode. What this means is that I will be dealing with ListNode pointers, which makes things more trickier.

To solve Issue #1, I created a method, called "preprocessLists", to make the two lists be the same size. I also created another method, called "addNumberToList", to add an int to a given linked list. The "addNumberToList" method returns a pointer to the newly added node to make it easier to use iterators and double-pointers in "preprocessLists". The side effect of "preprocessLists" is that it makes changes to the original list. I was unsure at the time of whether to not I should modify the original list, as I was told not to unless otherwise specified in school. Either way, I ended up doing it as the prompt did not say "don't change the original lists."

To solve Issue #2, I implemented an if-else chain to deal with varies situations with calculating a sum that was greater than or equal to 10.

To solve Issue #3, I ended up using the given struct since LeetCode will be using it when judging my code. It was difficult to get use to using structs and pointers to make up my lists as I am used to using the C++ STL "list" class.

The Results

After solving the three main issues and fixing a few bugs, I have managed to provide a working "addTwoNumbers" method that satisfied LeetCode's judging!

 I was surprised to get 12 ms of runtime as I feel like I used too many loops. However, I still need to develop my sense of what is "fast" and what is "slow" when it comes to benchmarking.

Conclusion

That will conclude today's post. This problem allowed me to practice using linked lists, single and double pointers, and developing algorithms. I hope you enjoyed reading through this post. I am currently working on another LeetCode problem, so expect a new post soon. Until then, thank you for reading!

Link to source code: https://github.com/EricFlorin/Leetcode-Solutions/blob/master/Add%20Two%20Numbers.cpp