Add 1 to a number represented as a linked list

Given a number which is represented in linked list, write a functio that will add 1 to the number

Example

INPUT
8->4->5 //Number is 845

OUTPUT
8->4->6 //After adding 1 the number is 846

Method 1

Algorithm

1. Reverse the given linked list

2. traverse the reversed linked list, add 1 to the first node(ie, sum = 1 + newhead->data). Insert the sum in result linked list(insert at beginning).

3. If the sum is greater than 10, then insert (sum - 10) to the result and update carry(ie, carry =1) for the next calculation.

4. print result

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
//Protype
void insertAtBeginning(LLNode**head,int dataToBeInserted);
// Function to reverse the linked list //
LLNode *reverse(LLNode *head)
{
    LLNode * prev   = NULL;
    LLNode * current = head;
    LLNode * next;
    while (current != NULL)
    {
        next  = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
// Adds one to the number which is represented in list
LLNode* addOne (LLNode* head)
{
    LLNode* result = NULL; // result is head node of the resultant list
    LLNode *temp, *prev = NULL;
    int carry = 1, sum;
    LLNode* newhead = reverse(head);
 
    while (newhead != NULL) //Till list becomes empty
    {
        //Next didgit is the sum of carry and current digit
        sum = carry + newhead->data;
 
        // update carry for next calulation
        // update sum if it is greater than 10
        if (sum>=10)
        {
          sum = sum - 10;
          carry = 1;
        }
        else
          carry =0;
        //Inserting sum at the begining of result
        insertAtBeginning(&result, sum);
        newhead = newhead->next;
    }
 
    if (carry > 0)
      insertAtBeginning(&result, 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 *head = NULL; //initial list has no elements

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

    cout<<"Number represented by list is 845"<<endl;
	display(&head);
  
	result = addOne(head);
	cout<<"After adding 1 to the number"<<endl;
	display(&result);
	return 0;
}
Try It

Method 2

In this method there is no need to reverse the linked list. We will use recursion

Algorithm

1. Recursively reach last node and forward carry to previous nodes

2. At the end end if there is a carry, then just insert carry at the begining of the list.

C++ Program

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

struct LLNode{
    int data;
    LLNode *next;   
};
//Protype
void insertAtBeginning(LLNode**head,int dataToBeInserted);
// Recursively add 1 from end to beginning and returns
// carry after all nodes are processed.
int recAdd(LLNode *head)
{
    // If linked list is empty, then
    // return carry
    if (head == NULL)
        return 1;
 
    // Add carry returned be next node call
    int res = head->data + recAdd(head->next);
 
    // Update data and return new carry
    head->data = (res) % 10;
    return (res) / 10;
}
 
// This function mainly uses addWithCarry().
LLNode* addOne(LLNode *head)
{
    // Add 1 to linked list from end to beginning
    int carry = recAdd(head);
 
    //if there is a carray at end. add carry to the list
    if (carry)
    {
        insertAtBeginning(&head, carry);
    }
 
    return head;
}
 
// 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 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 *head = NULL; //initial list has no elements

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

    cout<<"Number represented by list is 845"<<endl;
    display(&head);
  
    result = addOne(head);
    cout<<"After adding 1 to the number"<<endl;
    display(&result);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top