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.
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.
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:
pointerwhich 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
Write a function that accepts two arguments:
- linked list a
- 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.
I define 2 variables as pointers:
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:
b and set them each to
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
I used a
while loop that runs until
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.
I refactored the variable names to read more explicitly in an effort to make clear what is taking 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!