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 contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
Keep track of the carry using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.\n
Figure 1. Visualization of the addition of two numbers: .
\nEach node contains a single digit and the digits are stored in reverse order.
Just like how you would sum two numbers on a piece of paper, we begin by summing the least-significant digits, which is the head of and . Since each digit is in the range of , summing two digits may "overflow". For example . In this case, we set the current digit to and bring over the to the next iteration. must be either or because the largest possible sum of two digits (including the carry) is .\n
The pseudocode is as following:\n
Note that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head\'s value.\n
Take extra caution of the following cases:\n
|When one list is longer than the other.\n|
|When one list is null, which means an empty list.\n|
|The sum could have an extra carry of one at the end, which is easy to forget.\n|
Time complexity : . Assume that and represents the length of and respectively, the algorithm above iterates at most times.\n
Space complexity : . The length of the new list is at most .\n
What if the the digits in the linked list are stored in non-reversed order? For example:\n