Add 2 numbers represented by linked lists and return the result in linked list

Here the trick is last element is linked list represents ones digit, last but one represents tens digit, etc. head is pointing to highest place value digit.

639 is represented as:

6 ->3 ->9

800 is represented as:

8 ->0 ->0

There are multiple approaches to compute this result:

· Make the lists with same number of elements. If any list is having less compared to another list, add 0s as new elements to the list. Use recursion, so that addition starts with last element. This approach involves:

o Going through each list separately: time complexity is O(n1) + O(n2)

o Adding new elements to one list: space complexity is O(|n1-n2|), time complexity is O(|n1-n2|)

o Then calling function in recursively: time complexity is O(max(n1,n2)), space complexity O(max(n1,n2)), space complexity is O(number of elements in result)

· Use stacks to push each list elements. Pop each element from each stack and do addition. This approach involves:

o Framing stacks: time complexity O(max(n1,n2)), space complexity is O(n1) + O(n2)

o Pop each element from each stack and do addition: time complexity is O(max(n1,n2)), space complexity is O(number of elements in result)

· Reverse each list , then do addition by going through each node in each list. This approach involves:

o Reversing linked lists: time complexity is O(max(n1,n2). Space complexity is O(1)

o Going through each list and do addition, time complexity is O(max(n1,n2)), space complexity is O(number elements in new list)

So, 3rd approach is comparatively better.

Following code snippet shows how to add numbers by reversing each list: