Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Symmetric Tree | Interview Problem

Introduction: In this tutorial we are going to solve a good question which will clear your doubts on how BFS or level order traversal is useful to solve binary tree problems. this is basically a question from Leetcode, and it is really very good problem to practice BFS. Problem Statement: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: But the following [1,2,2,null,3,null,3] is not: Link : Leetcode Link please make binary tree on paper by the given array above. and you will get a clear picture of the problem. what we are going to do in this problem. Solution: As we know we are going to apply BFS to solve this problem. actually you have to just get one thing to solve this problem. we will perform BFS, but with little change or modification. So first we will store the root->val in a vector or array of the left subtree. and during this we will first insert left child and then ...
Post a Comment
Read more

Construct Binary Tree from preorder and inorder | Data Structure

Introduction: In this tutorial we are going to see how we can construct the binary tree from given preorder and inorder. Prerequisites: you should know about binary tree traversal and on paper you can draw binary tree from given preorder and inorder traversal. Inorder:left->root->right; Preorder:root->left->right; Problem Statement: we have given two arrays. one for preorder and another for inorder. by using these two array we have to built a binary tree. eg: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] solution: Solution: We will follow recursive approach to solve this question.let's discuss how we can solve it. Trick: In the given preorder the very first element will be the root of the tree. then we will find root element in inorder also. and we know in inorder traversal we have left part then root and then right part of the tree. by using preorder we can get the root of the main tree and by using inorder and root we can get the left part and right part of the...
Post a Comment
Read more

Linked List Data Structure | Creation and Traversal

Introduction: In this tutorial we will create our linked list. Before writing code let's understand key words related to linked list: 1. Head:    first node of the linked list is called the head of the list. and this node is most important. 2.Tail:       last node is called the tail of the list which must points to  null.            step1: For creating the list first of all let's declare the structure of Nodes of the list: struct Node{ int val; struct Node *next; } step2: write main function: int main(){     int n;     cout<<"enter the number of Nodes:";     cin>>n;     struct Node* head = NULL;     struct Node* temp;     int m;     while(n--){         cout<<"enter the data into nodes:";         cin>>m;    ...
1 comment
Read more