This is another simple problem that deals with linked list traversals and carrying forward the addendum.
Input :
l1 = [9,9,9,9,9,9,9],
l2 = [9,9,9,9]
Two Lists can be added just like the regular summation with LSB starting from beginning of the list.
9,9,9,9,9,9,9
9,9,9,9
=================
8,9,9,9,0,0,0,1
=================
Two lists are stored in reverse order and so LSB starts from beginning of the list.
O(n) algorithm for the addition of two numbers can be found below.
1. Start simultaneously from the beginning of each of the two lists and add the integers.
2. Carry forward the addendum and store the summation result.
3. Create new ListNode and store the summation result value and append the new node to the result list.
4. At least one of the lists will end upon the traversal and break out of the loop.
5. Figure out the reminder of one of the lists and add the addendum value to that list to arrive at final result.
This should work out in O(n) time complexity.
O(n) algorithm code can be found @ Add Two Numbers – LeetCode
– Vamshi.
LeetCode Algorithms Solved 