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
</br>
Solution
The main issue here is to consider that the sum of two number may overflow, which is to say the sum is above 10; therefore, we have to carry the 10 to the next digit. And the maximum possible sum of the two numbers can be 19, so the carry can be either 1 or 0.
Other than that, we only have to take care of the pointer and watch out some special cases like empty lists, different length and possible extra carry to the end.
The code is shown as below.
Java
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode p=l1,q=l2,curr=dummy;
int carry = 0;
while(p != null || q !=null)
{
int x = p != null ? p.val:0;
int y = q != null ? q.val:0;
int sum = x+y+carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
if(p!=null) p = p.next;
if(q!=null) q = q.next;
curr = curr.next;
}
if(carry >0){
curr.next = new ListNode(carry);
}
return dummy.next;
}
}
</br>
Complexity Analysis
Time Complexity: O(n).
Space Complexity: O(n). For the creation of the new list.
</br>
