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)