Add 1 to a number represented as linked list.cpp

//{ Driver Code Starts
//Initial template for C++

#include <bits/stdc++.h> 
using namespace std; 

struct Node
{
    int data;
    struct Node* next;
    
    Node(int x){
        data = x;
        next = NULL;
    }
};

void printList(Node* node) 
{ 
    while (node != NULL) { 
        cout << node->data; 
        node = node->next; 
    }  
    cout<<"\n";
} 


// } Driver Code Ends
//User function template for C++

/* 

struct Node
{
    int data;
    struct Node* next;
    
    Node(int x){
        data = x;
        next = NULL;
    }
};

*/

class Solution
{
    public:
    Node* reverse(Node* root){
        if(root==NULL || root->next==NULL) return root;
        Node* prev=NULL;
        Node* curr=root;
        Node* forward=root;
        while(curr!=NULL){
            forward=curr->next;
            curr->next=prev;
            prev=curr;
            curr=forward;
        }
        return prev;
    }
    Node* addOne(Node *head) 
    {
        // Your Code here
        // return head of list after adding one
        
        Node* temp=head;
        temp=reverse(temp);
        int carry=1;
        head=temp;
        // cout<<temp->data<<endl;
        if(temp->data<9){
            temp->data=temp->data+1;
            head=reverse(head);
            return head;
        }
        
        while(temp!=NULL){
            // cout<<temp->data<<" ";
            int sum=temp->data+carry;
            
            if(sum>9){
                temp->data=0;
               
                carry=1;
            }else{
                temp->data=sum;
                carry=0;
                break;
            }
            if(temp->next==NULL) break;
            temp=temp->next;
        }
        // cout<<endl;
        if(carry!=0){
            temp->next=new Node(carry);
            
        }
        head=reverse(head);
        return head;
    }
};

//{ Driver Code Starts.

int main() 
{ 
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        
        Node* head = new Node( s[0]-'0' );
        Node* tail = head;
        for(int i=1; i<s.size(); i++)
        {
            tail->next = new Node( s[i]-'0' );
            tail = tail->next;
        }
        Solution ob;
        head = ob.addOne(head);
        printList(head); 
    }
    return 0; 
} 

// } Driver Code Ends