Subtract 1 from a number represented as Linked List

  

#include <bits/stdc++.h>

using namespace std;

  

class Node {

public:

    int data;

    Node* next;

};

  

Node* newNode(int data)

{

    

    Node* new_node = new Node;

    new_node->data = data;

    new_node->next = NULL;

  

    

    return new_node;

}

  

int subtractOneUtil(Node* head)

{

  

    

    if (head == NULL)

        return -1;

  

    

    

    int borrow = subtractOneUtil(

        head->next);

  

    

    if (borrow == -1) {

  

        

        

        if (head->data == 0) {

            head->data = 9;

            return -1;

        }

  

        

        

        else {

            head->data = head->data - 1;

            return 0;

        }

    }

  

    

    else {

        return 0;

    }

}

  

Node* subtractOne(Node* head)

{

  

    

    

    subtractOneUtil(head);

  

    

    

    while (head and head->next

           and head->data == 0) {

        head = head->next;

    }

  

    return head;

}

  

void printList(Node* node)

{

    

    while (node != NULL) {

        cout << node->data;

        node = node->next;

    }

    cout << endl;

}

  

int main()

{

    Node* head = newNode(1);

    head->next = newNode(0);

    head->next->next = newNode(0);

    head->next->next->next = newNode(0);

  

    cout << "List is ";

    printList(head);

  

    head = subtractOne(head);

  

    cout << "Resultant list is ";

    printList(head);

  

    return 0;

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets