Add, two, numbers, represented, linked, lists

Given two numbers which are represented by two lists, write a  funtion that will find the sum of two  numbers and prints the list which is the representation of the sum.

Example

INPUT :
list1: 3->2->1 //Number is 123
list2: 2->4->5 //Number is 542

OUTPUT :
sum: 5->6->6 //Sum is 665

Method 1 :

Time Complexity : O(m + n),

where m is the number of nodes in list1 and n is the number of nodes in list2.

Algorithm

1. Traverse through both lists

2. Add the elements in both lists ie, sum =  carry + list1element + list2element.

3. If the sum is greater than or equal to 10, then create a new node with (sum-10) as data and insert it in the result list and make carry =1

4. If sum is less than 10, then just create a new node with sum as the data and insert it in the result list.

5. Return the result list

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;	
};
//Creates a new node with given data
LLNode *newNode(int data)
{
    LLNode *new_node = new LLNode;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// Adds elements of two linked lists and return the head node of resultant list //
LLNode* addTwoLists (LLNode* list1, LLNode* list2)
{
    LLNode* result = NULL; // result is head node of the resultant list
    LLNode *temp, *prev = NULL;
    int carry = 0, sum;
 
    while (list1 != NULL || list2 != NULL) //while both lists exist
    {
        //calculating the sum of both elements in list1 and list2
        //If there there is no elment in any list, just only add element in other list
        sum = carry + (list1? list1->data: 0) + (list2? list2->data: 0);
 
        // update carry for next calulation
        // update sum if it is greater than 10
        if (sum>=10)
        {
          sum = sum - 10;
          carry = 1;
        }
        else
          carry =0;
 
        // Create a new node with sum as data
        temp = newNode(sum);
 
        // if this is the first node then set it as head of the resultant list
        if(result == NULL)
            result = temp;
        else // If this is not the first node then connect it to the rest.
            prev->next = temp;
 
        // Set prev for next insertion
        prev  = temp;
 
        // Move list1 and list2 pointers to next nodes
        if (list1) list1 = list1->next;
        if (list2) list2 = list2->next;
    }
 
    if (carry > 0)
      temp->next = newNode(carry);
 
    // return head of the resultant list
    return result;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next=NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	while(temp!=NULL) //till the list ends (NULL marks ending of list)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	LLNode *result = NULL;
	LLNode *list1 = NULL; //initial list has no elements

	insertAtBeginning(&list1,5);
	insertAtBeginning(&list1,4);
  insertAtBeginning(&list1,8);

  LLNode *list2 = NULL;
  insertAtBeginning(&list2,5);
  insertAtBeginning(&list2,2);
  insertAtBeginning(&list2,8);


	
	cout<<"\n Two lists are :-\n";
  cout<<"first number is 548"<<endl;
	display(&list1);
  cout<<"second number is 528"<<endl;
  display(&list2);
  
	result = addTwoLists(list1,list2);
	cout<<"After adding two lists sum is 1076"<<endl;
	display(&result);
	return 0;
}
Try It

Method 2 :

In the previous method, least significant digit is first node of lists and most significant digit is last node. In this problem, most significant node is first node and least significant digit is last node.

In this method we will not use any extra space or modify lists. we use recursion

Example

INPUT :
list1 : 3->2->1 //Number is 321
list2 : 2->4->5 //Number is 245

OUTPUT :
sum: 5->6->6//Sum is 566

Time Complexity: O(m + n),

where m is the number of nodes in list1 and n is the number of nodes in list2

Algorithm

1. Calculate the sizes of two lists

2. If sizes are same, then calculate sum using recursion. Hold all nodes in recursion call stack till the rightmost node, calculate sum of rightmost nodes and forward carry to left side.

3. If sizes are not same,

      a) Calculate difference of sizes of two linked lists. Let the difference be diff
  

      b) Move diff nodes ahead in the bigger linked list. Now use step 2 to calculate sum of     smaller list and right sub-list (of same size) of larger list. Also, store the carry of this sum.

      c) Calculate sum of the carry (calculated in previous step) with the remaining left sub-list of     larger list. Nodes of this sum are added at the beginning of sum list obtained previous step.

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
    int data;
    LLNode *next;   
};
//Protype
void insertAtBeginning(LLNode**head,int dataToBeInserted);
//Swaping the two pointers
void swapPointer(LLNode** a, LLNode** b )
{
    LLNode* temp = *a;
    *a = *b;
    *b = temp;
}
 
// function to get size of linked list //
int getSize(LLNode *list)
{
    int size = 0;
    while (list != NULL)
    {
        list = list->next;
        size++;
    }
    return size;
}
 
// Adds two linked lists of same size represented by list1 and list2 and returns
// head of the resultant linked list. 
// Carry is propagated while returning from the recursion
LLNode* ifSameSize(LLNode* list1, LLNode* list2, int* carry)
{
    // Since the function assumes linked lists are of same size,
    // check any of the two head pointers
    if (list1 == NULL)
        return NULL;
 
    int sum;
 
    // Allocate memory for result node of current two nodes
    LLNode* result = new LLNode;
 
    // Recursively add remaining nodes and get the carry
    result->next = ifSameSize(list1->next, list2->next, carry);
 
    // add digits of current nodes and propagated carry
    sum = list1->data + list2->data + *carry;
    *carry = sum / 10;
    sum = sum % 10;
 
    // Assign the sum to current node of resultant list
    cout<<sum;
    result->data = sum;
 
    return result;
}
 
// After the smaller list is added to the bigger lists's sublist of same size.  
//  the carry must be added to left side of larger list to get the final result.
void addCarryToRemaining(LLNode* list1, LLNode* cur, int* carry, LLNode** result)
{
    int sum;
 
    // If diff. number of nodes are not traversed, add carry
    if (list1 != cur)
    {
        addCarryToRemaining(list1->next, cur, carry, result);
 
        sum = list1->data + *carry;
        *carry = sum / 10;
        sum = sum % 10;
 
        // add this node to the front of the result
        insertAtBeginning(result, sum);
    }
}
 
// The main function that adds two linked lists represented by list1 and list2.
// The sum of two lists is stored in a list referred by result
void addTwoLists(LLNode* list1, LLNode* list2, LLNode** result)
{
    LLNode *cur;
 
    // If first list is empty
    if (list1 == NULL)
    {
        *result = list2;
        return;
    }
 
    // If second list is empty
    else if (list2 == NULL)
    {
        *result = list1;
        return;
    }
 
    int size1 = getSize(list1);
    int size2 = getSize(list2) ;
 
    int carry = 0;
 
    // Add same size lists
    if (size1 == size2)
        *result = ifSameSize(list1, list2, &carry);
 
    else
    {
        int diff = abs(size1 - size2);
 
        // First list should always be larger than second list.
        // If not, swap pointers
        if (size1 < size2)
            swapPointer(&list1, &list2);
 
        // move diff. number of nodes in first list
        for (cur = list1; diff--; cur = cur->next);
 
        // get addition of same size lists
        *result = ifSameSize(cur, list2, &carry);
 
        // get addition of remaining first list and carry
        addCarryToRemaining(list1, cur, &carry, result);
    }
 
    // if some carry is still there, add a new node to result
    if (carry)
        insertAtBeginning(result, carry);
}


void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
    LLNode*curr=new LLNode;
    //make a new node with this data and next pointing to NULL
    curr->data=dataToBeInserted;
    curr->next=NULL;

    if(*head==NULL) //if list is empty then set the current formed node as head of list
            *head=curr;
        
    else //make the next of the current node point to the present head and make the current node as the new head
        {
            curr->next=*head;
            *head=curr;
        }
        
        //O(1) constant time
}


void display(LLNode**head)
{
    LLNode*temp=*head;
    while(temp!=NULL) //till the list ends (NULL marks ending of list)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<" ->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

int main() 
{    
    LLNode *result = NULL;
    LLNode *list1 = NULL; //initial list has no elements

    insertAtBeginning(&list1,5);
    insertAtBeginning(&list1,4);
    insertAtBeginning(&list1,8);


    LLNode *list2 = NULL;
    insertAtBeginning(&list2,5);
    insertAtBeginning(&list2,2);
    insertAtBeginning(&list2,8);


    
    cout<<"\n Two lists are :-\n";
    cout<<"first number is 845"<<endl;
    display(&list1);
    cout<<"second number is 825"<<endl;
    display(&list2);
  
    addTwoLists(list1,list2,&result);
    cout<<"After adding two lists sum is 1670"<<endl;
    display(&result);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top