Linked Lists — Add Two Numbers

Today we are going to be looking at another linked list problem:

We will do different solutions for this problem. The first way is a naive approach but it gets the job done.

First we initialize two arrays representing both the linked lists and we traverse through both lists adding the value at each node to the respective array. Once we have the numbers that are in our linked lists we sum them together to get our total. We then have our answer we just need to return a linked list representing this number. We create a function that creates linked lists and then return the function.

Here is an example of this in action:

Next, we will see the optimal solution:

First, since we know we want to return a new linked list we will initialize a variable called dummyHead and set that equal to a new ListNode (this represents the beginning of our new linked list). Then we will set the curr to the dummyHead. We will make a while loop that will keep looping while either linked list still exists. We take the value at each node in each linked list and add them together, along with our carry variable. This variable represents either 0 or 1, depending on whether our previous two node numbers equaled more than 10. We set our curr.next equal to a new ListNode that is equal to the remainder of the sum divided by ten. Then we move forward in our new linked list and also move forward in each of the linked lists we are looking at. Then at the end if there is a carry that was leftover we need to add this to our new linked list. Then we will return the dummyHead.next as our result.