{"id":27625,"date":"2018-04-04T19:36:41","date_gmt":"2018-04-04T14:06:41","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27625"},"modified":"2018-09-16T14:37:36","modified_gmt":"2018-09-16T09:07:36","slug":"add-1-number-represented-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/add-1-number-represented-linked-list\/","title":{"rendered":"Cpp Algorithm-Add 1 to a number represented as linked list"},"content":{"rendered":"

Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0)<\/p>\n

Below are the steps :<\/p>\n

    \n
  1. Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.<\/li>\n
  2. Start traversing linked list from leftmost node and add 1 to it. If there is a carry, move to the next node. Keep moving to the next node while there is a carry.<\/li>\n
  3. Reverse modified linked list and return head.<\/li>\n<\/ol>\n

    C++ prpgramming:<\/strong><\/p>\n

    <\/div> 
    \/\/ C++ program to add 1 to a linked list#include<bits\/stdc++.h> \/* Linked list node *\/struct Node{    int data;    Node* next;}; \/* Function to create a new node with given data *\/Node *newNode(int data){    Node *new_node = new Node;    new_node->data = data;    new_node->next = NULL;    return new_node;} \/* Function to reverse the linked list *\/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;} \/* Adds one to a linked lists and return the head   node of resultant list *\/Node *addOneUtil(Node *head){    \/\/ res is head node of the resultant list    Node* res = head;    Node *temp, *prev = NULL;     int carry = 1, sum;     while (head != NULL) \/\/while both lists exist    {        \/\/ Calculate value of next digit in resultant list.        \/\/ The next digit is sum of following things        \/\/ (i) Carry        \/\/ (ii) Next digit of head list (if there is a        \/\/     next digit)        sum = carry + head->data;         \/\/ update carry for next calulation        carry = (sum >= 10)? 1 : 0;         \/\/ update sum if it is greater than 10        sum = sum % 10;         \/\/ Create a new node with sum as data        head->data = sum;         \/\/ Move head and second pointers to next nodes        temp = head;        head = head->next;    }     \/\/ if some carry is still there, add a new node to    \/\/ result list.    if (carry > 0)        temp->next = newNode(carry);     \/\/ return head of the resultant list    return res;} \/\/ This function mainly uses addOneUtil().Node* addOne(Node *head){    \/\/ Reverse linked list    head = reverse(head);     \/\/ Add one from left to right of reversed    \/\/ list    head = addOneUtil(head);     \/\/ Reverse the modified list    return reverse(head);} \/\/ A utility function to print a linked listvoid printList(Node *node){    while (node != NULL)    {        printf("%d", node->data);        node = node->next;    }    printf("\\n");} \/* Driver program to test above function *\/int main(void){    Node *head = newNode(1);    head->next = newNode(9);    head->next->next = newNode(9);    head->next->next->next = newNode(9);     printf("List is ");    printList(head);     head = addOne(head);     printf("\\nResultant list is ");    printList(head);     return 0;}<\/code><\/pre> <\/div>\n
    Output:<\/strong><\/p>\n
    List is 1999\r\n\r\nResultant list is 2000\r\n\r\n<\/pre>\n
    \u00a0Recursive Implementation:<\/strong>
    \nWe can recursively reach the last node and forward carry to previous nodes. Recursive solution doesn\u2019t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes.<\/p>\n
    C++ Programming:<\/strong><\/p>\n
     
     <\/div> 
    \/\/ Recursive C++ program to add 1 to a linked list#include<bits\/stdc++.h> \/* Linked list node *\/struct Node{    int data;    Node* next;}; \/* Function to create a new node with given data *\/Node *newNode(int data){    Node *new_node = new Node;    new_node->data = data;    new_node->next = NULL;    return new_node;} \/\/ Recursively add 1 from end to beginning and returns\/\/ carry after all nodes are processed.int addWithCarry(Node *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 + addWithCarry(head->next);     \/\/ Update data and return new carry    head->data = (res) % 10;    return (res) \/ 10;} \/\/ This function mainly uses addWithCarry().Node* addOne(Node *head){    \/\/ Add 1 to linked list from end to beginning    int carry = addWithCarry(head);     \/\/ If there is carry after processing all nodes,    \/\/ then we need to add a new node to linked list    if (carry)    {        Node *newNode = new Node;        newNode->data = carry;        newNode->next = head;        return newNode; \/\/ New node becomes head now    }     return head;} \/\/ A utility function to print a linked listvoid printList(Node *node){    while (node != NULL)    {        printf("%d", node->data);        node = node->next;    }    printf("\\n");} \/* Driver program to test above function *\/int main(void){    Node *head = newNode(1);    head->next = newNode(9);    head->next->next = newNode(9);    head->next->next->next = newNode(9);     printf("List is ");    printList(head);     head = addOne(head);     printf("\\nResultant list is ");    printList(head);     return 0;}<\/code><\/pre> <\/div>\n
    Output:<\/strong><\/p>\n
    List is 1999\r\n\r\nResultant list is 2000\r\n\r\n<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Cpp Algorithm-Add 1 to a number represented as linked list-Linked list
    \nNumber is represented in linked list such that each digit corresponds<\/p>\n","protected":false},"author":1,"featured_media":31292,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81891,81893,81885,81887,81886,81889,81888,81890,81894,81892,81884],"class_list":["post-27625","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linked-list","category-singly-linked-list","tag-1s-and-2s","tag-add-1-to-the-integer-represented-by-a-linked-list-with-on-time-and-o1-space","tag-add-2-linked-lists","tag-add-one-to-number-array","tag-add-two-linked-lists-c","tag-find-next-greater-element-with-same-digits","tag-get-a-number","tag-given-a-linked-list-of-0s","tag-how-to-find-if-words-in-a-file-are-anagram","tag-sort-it","tag-sum-of-two-linked-lists-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27625","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27625"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27625\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31292"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27625"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27625"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27625"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}