Add 1 to a number represented as linked list in C++

In this post, we will learn how to add 1 to a number represented as linked list in C++. For example 4959 is represented as (4-> 9-> 5 -> 9->9) and adding 1 to it should change it to (4->9->6->0->0).

Add 1 to a number represented as linked list in C++

In this approach we will follow the following steps:
1. At first linked list is reversed.
2. Then we add 1 to leftmost node in the linked list. And if there is a carry, we will move to the next node. We will keep traversing until the carry is 0.
3. Finally we will again reverse our modified linked list and then return head.

#include <bits/stdc++.h>
using namespace std;
class Node
{
    public:
    int data;
    Node* next;
    Node(int value){
     data=value;
     next=NULL;
    }
};

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 *addUtil(Node *head)
{
    Node* res = head;
    Node *temp, *prev = NULL;
    int sum;
    int carry = 1; 
    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 = new Node(carry);
    return res;
}
Node* add1One(Node *head)
{
    head = reverse(head);
    head = addUtil(head);
    return reverse(head);
}
void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data;
        node = node->next;
    }
    cout<<endl;
}
int main()
{
    Node *head = new Node(4);
    head->next = new Node(9);
    head->next->next = new Node(5);
    head->next->next->next = new Node(9);
    cout << "List is ";
    printList(head);
    cout<<endl;
    head = add1One(head);
    cout << "After adding 1 the new list is ";
    printList(head);
    return 0;
}

input:List is 4959
output:After adding 1 the new list is 4960