Add Two Numbers Represented by Linked List
In this class, We discuss Add Two Numbers Represented by Linked List.
The reader can take a complete competitive coding course. Click Here.
The reader can have basic coding skills to crack placement for service-based companies. Click Here.
Question:
Given two decimal numbers represented in the linked list.
The task is to return a linked list that represents the sum of the two numbers.
Example:
Input:
L1: 1-3-1-None
L2: 2-3-2-None
Output:
L3: 3-6-3-None
Example 2:
Input:
L1: 1-2-5-None
L2: 2-5-None
Output:
L3: 1-4-5-None
Logic:
We do this example in two ways.
1) Reversing the Linked List
2) Using a Recursive Function call
Both methods are explained in the video.
We are providing code for the first method.
The readers are suggested to write the code using the second method.
Code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Solution:
def reverse(self, head):
if head is None or head.next is None:
return head
prev = None
next = None
curr = head
while curr is not None:
next = curr.next
curr.next = prev
prev = curr
curr = next
head = prev
return head
def addTwoLists(self, first, second):
curr1 = self.reverse(first)
curr2 = self.reverse(second)
sum = 0
carry = 0
res = None
prev = None
while curr1 is not None or curr2 is not None:
sum = carry + (curr1.data if curr1 else 0) + \
(curr2.data if curr2 else 0)
carry = (1 if sum >= 10 else 0)
sum = sum % 10
temp = Node(sum)
if res is None:
res = temp
else:
prev.next = temp
prev = temp
if curr1:
curr1 = curr1.next
if curr2:
curr2 = curr2.next
if carry > 0:
temp.next = Node(carry)
ans = self.reverse(res)
return ans
n=int(input(“enter number of nodes”))
head1=None
head2=None
for i in range(n):
x=int(input(“enter data”))
ob=Node(x)
if(i==0):
head1=ob
else:
tmp=head1
while(tmp.next!=None):
tmp=tmp.next
tmp.next=ob
m=int(input(“enter number of nodes”))
for i in range(m):
x=int(input(“enter data”))
ob=Node(x)
if(i==0):
head2=ob
else:
tmp=head2
while(tmp.next!=None):
tmp=tmp.next
tmp.next=ob
ob1=Solution()
z=ob1.addTwoLists(head1,head2)
tmp=z
while(tmp.next!=None):
print(tmp.data)
tmp=tmp.next
print(tmp.data)