You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

`Input: l1 = [7,2,4,3], l2 = [5,6,4]Output: [7,8,0,7]`

Example 2:

`Input: l1 = [2,4,3], l2 = [5,6,4]Output: [8,0,7]`

Example 3:

`Input: l1 = [0], l2 = [0]Output: [0]`

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.

Follow up: Could you solve it without reversing the input lists?

Approach 1:

Reverse the list and then add the LSB first.

`def add(l1,l2):   reverse(l1,l2)   traverse the linked list and add each corresponding node,   if any node is exhausted , then assume its value as 0    go on adding the corresponding element together with carry from,   previous addition `

Time :O(n)

Space :O(n) new linked list representing the sum value

Approach 2:

Without reversing

Using stack

Since stack works on LIFO method.

We put all values of l1 and l2 to 2 seperate stacks, and pop the elements and add it with carry from previous addition.

Note that if any of the stack is emptied first while popping , then further values from that stack is assumed as 0.

`def add(l1,l2):  traverse the linked list     push l1 and l2 elements to the stack  pop the stack element and add them with carry  update new carry and also put the last digit of result to the new         linked list`

# The solution

`class Solution(object):    def addTwoNumbers(self, l1, l2):        ptr1,ptr2=l1,l2        one,two=[],[]        while(ptr1 or ptr2):            if ptr1:                one.append(ptr1.val)                ptr1=ptr1.next            if ptr2:                two.append(ptr2.val)                ptr2=ptr2.next        carry,temp=0,ListNode(0)        head=temp        while(one or two):            val1=one.pop() if one else 0             val2=two.pop() if two else 0             carry,rem=divmod(val1+val2+carry,10)            new_node=ListNode(rem)            new_node.next=temp.next            temp.next=new_node        if carry:            new_node=ListNode(carry)            new_node.next=temp.next            temp.next=new_node        return head.next`

Note that ,the result is such that the head of resulting linked list point to the MSB of sum.

So, while linking the nodes, new nodes are inserted at front , rather than at end.

Time :O(n)

Space :O(n+n) stack space and new linked list representing the sum value.

## More from Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.

Love podcasts or audiobooks? Learn on the go with our new app.

## Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.