ADD ONE TO THE NUMBER

In this article, we will learn how to add one to linked list. As we know inked list points to every next node as well as contains the address of the next node and sometimes adding one to linked list can also increase the length of the linked list. let’s try to understand the logic to add 1 to linked list.

How to add one to the number represented as linked list.

You are given a linked list representing a number such that each individual node acts as a digit of the number.
Example:

The list
HEAD->1->2->3->NULL corresponds to the number 123. You to add 1 to this number to get 124 i.e. 1->2->4.

See original problem statement here

EXPLANATION to add one to linked list:

Approach 1 to add 1 to linked list(Reverse the linked list):

Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.For this changed linked list now traverse the list, in the left-most node add one. if this node’s value is equal to 9 then propagate a carry to the next Node. Do the same procedure until the carry is there.
Reverse the string back as in original form and then returned the head to get the string printed.

 struct Node 
    { 
    int data; 
    Node* next; 
    }; 

     Node *newNode(int data) 
    { 
    Node *new_node = new Node; 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
    } 
    Node *reverse(Node *head) 
    { 
    Node * prev   = NULL; 
    Node * current = head; 
    Node * next; 
    while (current != NULL) 
    { 
        next  = current->next; 
        current->next = prev; 
        prev = current; 
        current = next; 
    } 
    return prev; 
    } 

    Node *addOneUtil(Node *head) 
    { 
    Node* res = head; 
    Node *temp, *prev = NULL; 

    int carry = 1, sum; 

    while (head != NULL) {
        sum = carry + head->data; 
        carry = (sum >= 10)? 1 : 0; 
        sum = sum % 10; 
        head->data = sum; 

        temp = head; 
        head = head->next; 
    } 
    if (carry > 0) 
        temp->next = newNode(carry); 

    return res; 
    } 

    Node* addOne(Node *head) 
    { 
    head = reverse(head); 
    head = addOneUtil(head); 
    return reverse(head); 
     } 
     void printList(Node *node) 
    { 
    while (node != NULL) 
    { 
        printf("%d", node->data); 
        node = node->next; 
    } 
    printf("\n"); 
    } 
    int main(void) 
    { int t;scanf("%d",&t);
     while(t--)
    {
      char s[100000];
    scanf("%s",s);
    int x=s[0]-'0';
    Node* head1=newNode(x);
    Node* head=head1;
    for(int i=1;i<strlen(s);i++)
    {
      head1->next=newNode(s[i]-'0');
      head1=head1->next;
    }
    head = addOne(head); 

    printList(head); }

    return 0; 
    } 
 #include <bits/stdc++.h>
     using namespace std;
     struct Node 
    { 
    int data; 
    Node* next; 
    }; 

    Node *newNode(int data) 
    { 
    Node *new_node = new Node; 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
    } 
    Node *reverse(Node *head) 
    { 
    Node * prev   = NULL; 
    Node * current = head; 
    Node * next; 
    while (current != NULL) 
    { 
        next  = current->next; 
        current->next = prev; 
        prev = current; 
        current = next; 
    } 
    return prev; 
     } 

    Node *addOneUtil(Node *head) 
      { 
    Node* res = head; 
    Node *temp, *prev = NULL; 

    int carry = 1, sum; 

    while (head != NULL){ 
        sum = carry + head->data; 
        carry = (sum >= 10)? 1 : 0; 
        sum = sum % 10; 
        head->data = sum; 

        temp = head; 
        head = head->next; 
    } 
    if (carry > 0) 
        temp->next = newNode(carry); 

    return res; 
     } 

     Node* addOne(Node *head) 
    { 
    head = reverse(head); 
    head = addOneUtil(head); 
    return reverse(head); 
    } 
     void printList(Node *node) 
    { 
    while (node != NULL) 
    { 
        cout<<node->data; 
        node = node->next; 
    } 
    printf("\n"); 
     } 
       int main(void) 
    { int t;scanf("%d",&t);
    while(t--)
    {
      string s;
    cin>>s;
    int x=s[0]-'0';
    Node* head1=newNode(x);
    Node* head=head1;
    for(int i=1;i<s.length();i++)
    {
      head1->next=newNode(s[i]-'0');
      head1=head1->next;
    }
    head = addOne(head); 

    printList(head); }

    return 0; 
    } 
 class prepbytes 
    { 
static class Node  
{  
    int data;  
    Node next;  
} 
static Node newNode(int data)  
{  
    Node new_node = new Node();  
    new_node.data = data;  
    new_node.next = null;  
    return new_node;  
}
static Node reverse(Node head)  
{  
    Node prev = null;  
    Node current = head;  
    Node next = null;  
    while (current != null)  
    {  
        next = current.next;  
        current.next = prev;  
        prev = current;  
        current = next;  
    }  
    return prev;  
}  
static Node addOneUtil(Node head)  
{  
    Node res = head;  
    Node temp = null, prev = null;  
    int carry = 1, sum;  
    while (head != null)
    {
        sum = carry + head.data;  
        carry = (sum >= 10)? 1 : 0;  
        sum = sum % 10;  
        head.data = sum;  
        temp = head;  
        head = head.next;  
    }  
    if (carry > 0)  
        temp.next = newNode(carry);  
    return res;  
} 
static Node addOne(Node head)  
{ 
    head = reverse(head);  
    head = addOneUtil(head);  
    return reverse(head);  
} 
static void printList(Node node)  
{  
    while (node != null)  
    {  
        System.out.print(node.data);  
        node = node.next;  
    }  
    System.out.println();  
}  
//main 
}  

# your code goes here
class Node:
 
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Function to reverse the linked list
    def reverse(self):
        prev = None
        current = self.head
        while(current is not None):
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev
 
    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    # Utility function to print the LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data,end=" ")
            temp = temp.next
 
 
# Driver program to test above functions
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
 
print ("Given Linked List")
llist.printList()
llist.reverse()
print ("\nReversed Linked List")
llist.printList()

Approach 2 to add 1 to linked list(Recursive):

Recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list.

#include <bits/stdc++.h>
    using namespace std;
    struct node{
    int data;
    node* next;
     };
    node* newnode(int x)
    {
     node* temp=new node();
     temp->data=x;
     temp->next=NULL;
     return temp;
    }
     node* reverse(node* head)
    {
     if(head==NULL||head->next==NULL)
     return head;
     node* rest=reverse(head->next);
      head->next->next=head;
     head->next=NULL;
     return rest;
     }
     int main()
    {
     int t;cin>>t;
     while(t--)
    {
    string s;
    cin>>s;
    int x=s[0]-'0';
    node* head1=newnode(x);
    node* head=head1;
    for(int i=1;i<s.length();i++)
    {
      head1->next=newnode(s[i]-'0');
      head1=head1->next;
    }
     node* headnew=reverse(head);
    int carry=1,sum=0;node* prev,*head2=headnew;
    while(headnew!=NULL)
    {
    sum=headnew->data+carry;
    carry=sum/10;
    headnew->data=sum%10;
    //cout<<sum%10<<" ";
    prev=headnew;
    headnew=headnew->next;
    }
     if(carry)
    {
    prev->next=newnode(carry);
    prev=prev->next;
    }
     node* headnew2=reverse(head2);
     while(headnew2!=NULL)
    {
    cout<<headnew2->data;
    headnew2=headnew2->next;
    }
     cout<<"\n";}
     return 0;
    }
class prepbytes { 
    static class Node 
    { 
        int data; 
        Node next; 
    } 
    static Node newNode(int data)  
    { 
        Node new_node = new Node(); 
        new_node.data = data; 
        new_node.next = null; 
        return new_node; 
    } 
    static int addWithCarry(Node head) 
    { 
        if (head == null) 
            return 1; 
        int res = head.data + addWithCarry(head.next); 
        head.data = (res) % 10; 
        return (res) / 10; 
    }  
    static Node addOne(Node head) 
    { 
        int carry = addWithCarry(head); 
        if (carry > 0) 
        { 
            Node newNode = newNode(carry); 
            newNode.next = head; 
            return newNode;  
        } 

        return head; 
    } 
    static void printList(Node node) 
    { 
        while (node != null) 
        { 
            System.out.print(node.data); 
            node = node.next; 
        } 
        System.out.println(); 
    } 
    //main
      }

# your code goes here
class Node:
 
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    def reverseUtil(self, curr, prev):
 
        # If last node mark it head
        if curr.next is None:
            self.head = curr
 
            # Update next to prev node
            curr.next = prev
            return
 
        # Save curr.next node for recursive call
        next = curr.next
 
        # And update next
        curr.next = prev
 
        self.reverseUtil(next, curr)
 
    # This function mainly calls reverseUtil()
    # with previous as None
 
    def reverse(self):
        if self.head is None:
            return
        self.reverseUtil(self.head, None)
 
    # Function to insert a new node at the beginning
 
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    # Utility function to print the LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data,end=" ")
            temp = temp.next
 
 
# Driver program
llist = LinkedList()
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
 
print("Given linked list")
llist.printList()
 
llist.reverse()
 
print("\nReverse linked list")
llist.printList()

In this blog, we have explained how to add one to linked list. We have explained two different approaches first one is by reversing the list and another one is recursive and also explained the updation of the carry variable corresponds with the sum variable and code implementation in various languages as well.T brush up your skills in a linked list, you can check out MYCODE | Competitive Programming.

FAQs related to add one to linked list.

1. When we update the carry variable while adding one to the linked list?
When the sum becomes more than 10 then carry is 1 else it is 0.

2. Can a LinkedList store different data types?
Yes, it’s allowed as long as the list is declared as List <Object> or List <Serializable>, which both String and Integer extend/implement

3. Is the linked list homogeneous?
The linked list is a dynamic data structure that stores homogeneous data elements

Leave a Reply

Your email address will not be published. Required fields are marked *