DIY: Add Two Numbers
Solve the interview question "Add Two Numbers" in this lesson.
We'll cover the following...
Problem statement
Given two non-empty linked lists that represent two non-negative integers, you have to add the two numbers and return the sum as a linked list. The digits are stored in reverse order, and each of their nodes contains a single digit.
Note: You may assume that the two numbers do not contain any leading zero, except the number
0itself.
Constraints
- The number of nodes in each linked list is in the range
[1, 100]. 0 <= Node->val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
Input
The function will take two linked lists, which will contain non-negative integers in the reverse order, as inputs. The following is an example of an input:
3 -> 4 -> 6
2 -> 8 -> 1
Output
The function should return the sum of the two linked lists given above in another linked list.
5 -> 2 -> 8
You may want to take extra care for the following cases:
| Test case | Explanation |
|---|---|
list1 = [1, 2] list2 = [1, 3, 5] |
When one list is longer than the other |
list1 = [] list2 = [2, 4] |
When one list is null, that is, the list is empty |
list1 = [9, 9] list2 = [9, 9] |
When the sum has an extra carry of one at the end |
Coding exercise
In this coding exercise, you need to implement the add_two_numbers(list11, list2) function, where list1 and list2 are linked lists. The function should return the sum of the two linked lists in the form of another linked list, as output.