Linked List Data Structure | Add Two Number Explanation

Introduction:

In this tutorial, we are going to solve a very famous problem on Linked List.

It is also an important question for coding interview. so let's see the problem and understand it in detail.

Problem Statement:

There are two numbers and each digit of number is represented by a node of linked list.and we have to add these two numbers, which is given in the form of linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

eg: num1 = 2354;

      num2 = 875;

see the image below:

Solution:

Now let's solve it. In this problem there may be three possibilities.

First:

Number of Nodes in the first linked list is greater than second linked list.

Second:

Number of Nodes in first linked list is less than second list.

Third:

Number of Nodes in the both linked list is equal.

Here number of nodes means number of digits in both number.

Another thing we have to keep in mind is that if we add two digits then there may be possibility of generating a carry during the addition. that mean if we add 5 and 7 then it will produce 2 and 1 as carry.

so we have to keep in mind all above points.

We can add two digits and insert it into one of those linked list nodes. or after each addition we will create a new node and store it's result into the new node. this is another approach. i am using second approach for making it simple.

Full Code:

 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
       ListNode *ans=NULL;
        ListNode *head;//head of new list
        int carry=0;
        while(l1!=NULL && l2!=NULL){
            int x=(l1->val+l2->val+carry)%10;//addition
            carry=(l1->val+l2->val+carry)/10;//check carry
            ListNode *temp=new ListNode(x);//create new node
            temp->next=NULL;
            if(ans==NULL){
                ans=temp;
                head=ans;
            }
            else{
                ans->next=temp;
                ans=temp;
            }
            l1=l1->next;
            l2=l2->next;
        }
        while(l1!=NULL){
              
                int val=(l1->val+carry)%10;
                carry=(l1->val+carry)/10;
           
                 ListNode *temp=new ListNode(val);
                 temp->next=NULL;
                ans->next=temp;
            ans=temp;
            l1=l1->next;
        }
         while(l2!=NULL){
               int val=(l2->val+carry)%10;
                carry=(l2->val+carry)/10;
           
                 ListNode *temp=new ListNode(val); 
             temp->next=NULL;
            ans->next=temp;
            ans=temp;
             l2=l2->next;
        }
         if(carry){
            ListNode* temp=new ListNode(carry);
            temp->next=NULL;
            ans->next=temp;
            ans=temp;
        }
       return head;
    }

so basically what we are doing in this code is, we are taking one node of both linked list, which is present at the same position, we are adding the value of both node and taking a mod of 10, because if the sum will be greater than 9 then we will keep only last digit of sum.

To check there is carry or not, we are dividing the sum(int x) by 10.

now after finding sum and carry, we are creating a new node, putting the value of sum into newly created node.

We are using two while loops:

first while loop will handle the situation when number of nodes in the first linked list is greater than second.

    while(l1!=NULL){
              
                int val=(l1->val+carry)%10;
                carry=(l1->val+carry)/10;
           
                 ListNode *temp=new ListNode(val);
                 temp->next=NULL;
                ans->next=temp;
            ans=temp;
            l1=l1->next;
        }

second while loop will handle the situation, when number of nodes in the second linked list is greater than first.

while(l2!=NULL){
               int val=(l2->val+carry)%10;
                carry=(l2->val+carry)/10;
           
                 ListNode *temp=new ListNode(val); 
             temp->next=NULL;
            ans->next=temp;
            ans=temp;
             l2=l2->next;
        }

now at the end all values of sum is inserted into a new list. which we can track using the head variable.

actually we storing the sum values into a new list.

i hope you got my points.still having any query then you can comment it down.

best of luck.