Leetcode: Add Two Numbers

Instructions

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.

Before we breakdown what the problem is asking, let's first discuss what a linked list is.

Linked List

A linear data structure of nodes chained together by pointers whose order is not determined by a physical location in memory. Each node in the list contains a data field and a reference to the next node in the list.

A linear data structure? Sounds like an array. Yes, but mostly no. Depending on the programming language, arrays tend to be of fixed size--though not the case in JavaScript. It is also very expensive to modify an array. The space for updating and/or removing elements must be created and shifted depending on which index you're operating on.

The advantages of linked lists attribute to their dynamic size and ease of modification, specifically insertion and deletion.

The disadvantages should be considered as followed: random access is not allowed so you must access elements in sequential order. Extra memory space is required for the pointer on each element of list. Linked lists are not cache friendly being that there is no physical reference point to find a node like an index.

There are 3 types of linked lists: Singly, Doubly and Circular. We'll be working with a Singly Linked List.

Each node is made up of at least two properties:

1. the data
2. a pointer which is a reference to the next node in line.

The first node is referred to as the head. If a linked list is empty, the value of the head is null.

What is Being Asked?

Write a function that accepts two arguments:

1. linked list a
2. linked list b

Both input lists contain whole numbers and are pointing in reverse meaning they're moving left bound. We must apply basic mathematics and add them together, then return the sum as its own linked list.

What Does That Look Like?

What Do I Need to Solve?

I define 2 variables as pointers: pointerA and pointerB and set them to an input list of their own.

I define 2 more variables as containers for the node values that we need to add: a and b and set them each to 0.

I also define a variable to store a value to carry over 1 like the example above.

We need to return a new linked list. I define a result variable and set it to a newly instantiated node list which points the head of the list. Then create an additional variable to represent the currentNode being operated on and point it to the result variable.

I used a while loop that runs until pointerA OR pointerB is not truthy, meaning that it will continue to loop until both lists run out of nodes. Inside of the while block is a series of conditionals explained in the comments.

Solution

Conclusion

I refactored the variable names to read more explicitly in an effort to make clear what is taking place throughout each iteration. Would you have solved it the same or did you go with a different approach? Do you have any suggestions on a refactor that may work better? Drop a comment! I'm interested to hear what you think.

As always thank you for reading and I look forward to interacting and sharing more code!