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.
Iterate through both of the linked lists at once. Determine any carry-over while adding. Add the carry-over to the addition on the right. If one linked list is longer than the other, extend the other linked list with nodes of value 0 and continue adding.
Keep track of the two values (one from each linked list) and the potential carry-over value.
While both linked lists have a 'next' node:
If only one linked list is exhausted, set that value to be '0'
Add up the two values
Determine whether there is carry-over
If there is carry-over, save it for the next addition
Return the head of the new linked list.
For example: l1 = [2 --> 4 --> 3]; l2 = [5 --> 6 --> 4 --> 5]
value1 = 2; value2 = 5; carry-over = 0 (default value for carry-over)
addition_value = 2 + 5 + 0 = 7
addition_linked_list = [7]
value1 = 4; value2 = 6; carry-over = 1
addition_value = 4 + 6 + 0 (no carry-over from previous addition)
addition_linked_list = [7 --> 0]
value1 = 3; value2 = 4; carry-over = 0
addition_value = 3 + 4 + 1 = 8
addition_linked_list = [7 --> 0 --> 8]
value1 = 'null' = 0 (set to default value since there is no next node); value2 = 5; carry-over = 0
addition_value = 0 + 5 + 0 = 5
addition_linked_list = [7 --> 0 --> 8 --> 5]