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.