Lesson

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order, and each node of the linked lists contains a single digit. Add the two numbers and return the sum as a linked list.

Write a function that takes in two linked lists representing non-negative numbers, and returns a linked list representing the sum of the two numbers.

Example Input:

``````LinkedList1: 6 -> 7 -> 3
LinkedList2: 8 -> 9 -> 4``````

Example Output:

``LinkedList: 4 -> 7 -> 8``

## Walkthrough

### Solution Explanation

The function
``addTwoNumbers``
takes in two linked lists representing non-negative numbers, and returns a linked list representing the sum of the two numbers. We start by initializing a
``result``
``current``
node that points to the
``result``
linked list. We also initialize a
``carry``
variable to keep track of any carryover that we need to add to the next node in the list.
We then loop through the linked lists as long as either
``l1``
or
``l2``
has a value, or if there is a carryover. In each iteration, we add the value of the nodes of
``l1``
and
``l2``
, as well as the carryover from the previous iteration. If the sum is greater than or equal to 10, we set
``carry``
to 1, otherwise we set it to 0. We then create a new node with the sum modulo 10, which is the single digit that we need to add to the
``result``
linked list. We then set the
``current``
node's
``next``
property to the new node, and move
``current``
to the next node.
We then move
``l1``
and
``l2``
to their next nodes, or to
``null``
if they have no more nodes. We continue looping until we reach the end of both linked lists and there is no carryover left.
We then return the
``result``
``next``
property, which is the actual start of the linked list.

Big O Complexity Analysis:

The time complexity of this function is O(max(m, n)), where
``m``
and
``n``
are the lengths of
``l1``
and
``l2``
, respectively. This is because we need to loop through both linked lists, and the number of iterations is determined by the longer of the two linked lists.

The space complexity of this function is O(max(m, n)), because we need to create a new linked list to store the result, and the number of nodes in the linked list is determined by the longer of the two linked lists.