ADD ONE TO THE NUMBER

Concepts Used

Linked list reversal

Difficulty Level

Medium.

Problem Statement :

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:

Approach 1(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;inext=newNode(s[i]-'0');
      head1=head1->next;
    }
    head = addOne(head); 

    printList(head); }

    return 0; 
    } 
 #include 
     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<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;inext=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(Recursive):

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

#include 
    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;inext=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<next;
    }
     if(carry)
    {
    prev->next=newnode(carry);
    prev=prev->next;
    }
     node* headnew2=reverse(head2);
     while(headnew2!=NULL)
    {
    cout<data;
    headnew2=headnew2->next;
    }
     cout<<"\n";}
     return 0;
    }

# 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()
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
      }

[forminator_quiz id="1489"]

This article tried to discuss Linked list reversal. Hope this blog helps you understand and solve the problem. To practice more problems on Linked list you can check out MYCODE | Competitive Programming.

Leave a Reply

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