# Add Two Numbers ii

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.