Add 1 To Number Represented As Linked List

#include<bits stdc++.h="">
using namespace std;
class Node
{
public:
    int data;
    Node *next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};
Node* addOne(Node* head_ref)
{
    Node* res = head_ref; // res will point to the head of the resultant list.


    int carry = 1 , sum;//Why carry is taken as 1 ? => because we need to add 1

    Node* prev; // prev pointer is necessary for the last node, if at last carry is there, we need to add a new Node with value carry.
    // (Take example of 9->9->9->9)

    while (head_ref != NULL) {
        sum = carry + head_ref->data;

        carry = (sum >= 10) ? 1 : 0;

        head_ref->data = (sum % 10);

        prev = head_ref;
        head_ref = head_ref->next;

    }
    if (carry > 0) {
        prev->next = new Node(carry);
    }

    return res;
}
Node*  reverseList(Node* head_ref) {
    Node* curr = head_ref;
    Node* prev = NULL, *next;

    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;

        prev = curr;
        curr = next;
    }

    return prev;
}
Node* addOneToList(Node* head_ref)
{
    head_ref = reverseList(head_ref);

    head_ref = addOne(head_ref);

    head_ref = reverseList(head_ref);

    return head_ref;
}

void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{
    Node* head = new Node(1);
    head->next = new Node(9);
    head->next->next = new Node(9);
    head->next->next->next = new Node(9);
    head->next->next->next->next = new Node(9);

    head = addOneToList(head);
    printList(head);
    return 0;
}

class CarryOne {
 
    /* Linked list node */
    static class Node
    {
        int data;
        Node next;
    }
 
    /* Function to create a new node with given data */
    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;
 
        // 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().
    static Node addOne(Node head)
    {
        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 > 0)
        {
            Node newNode = newNode(carry);
            newNode.next = head;
            return newNode; // New node becomes head now
        }
 
        return head;
    }
 
    // A utility function to print a linked list
    static void printList(Node node)
    {
        while (node != null)
        {
            System.out.print(node.data);
            node = node.next;
        }
        System.out.println();
    }
 
    /* Driver code */
    public static void main(String[] args)
    {
        Node head = newNode(1);
        head.next = newNode(2);
        head.next.next = newNode(2);

        System.out.print("List is ");
        printList(head);
 
        head = addOne(head);
        System.out.println();
        System.out.print("Resultant list is ");
        printList(head);
    }
}

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

def newNode(data):
	return Node(data)

def reverseList(head):
	if not head:
		return
	curNode = head
	prevNode = head
	nextNode = head.next
	curNode.next = None

	while(nextNode):
		curNode = nextNode
		nextNode = nextNode.next
		curNode.next = prevNode
		prevNode = curNode

	return curNode

def addOne(head):

	head = reverseList(head)
	k = head
	carry = 0
	prev = None
	head.data += 1

	while(head != None) and (head.data > 9 or carry > 0):
		prev = head
		head.data += carry
		carry = head.data // 10
		head.data = head.data % 10
		head = head.next

	if carry > 0:
		prev.next = Node(carry)
	return reverseList(k)

def printList(head):
	if not head:
		return
	while(head):
		print("{}".format(head.data), end=" ")
		head = head.next


if __name__ == '__main__':
	head = newNode(1)
	head.next = newNode(9)
	head.next.next = newNode(9)
	head.next.next.next = newNode(9)
	head = addOne(head)
	printList(head)

#include<bits stdc++.h="">
using namespace std;
class Node
{
public:
    int data;
    Node *next;

    Node(int val) {
        data = val;
        next = NULL;
    }
};
void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
Node* addOneToList(Node* head)
{
    Node* last = NULL , *current_node = head;

    //Through this loop we will find the last non-nine node.
    while (current_node->next != NULL)
    {
        if (current_node->data != 9) {
            last = current_node;
        }
        current_node = current_node->next;
    }


    //This loop will run till the second last node, so for the last node we will check using if condition.
    //If the last node itself is not 9. Then simply increment the value by 1 and return the head.
    if (current_node->data != 9) {
        current_node->data++;
        return head;
    }

    //After loop if last is still NULL, that means there is no value which is not 9.
    //For example 9->9->9->9
    if (last == NULL) {
        //1 extra node will be needed.
        last = new Node(1);
        last->next = head;
        head = last;

        //then make every node 0
        last = last->next;
        while (last != NULL) {
            last->data = 0;
            last = last->next;
        }
        return head;
    }

    //Last case => when the non-nine node is somewhere in middle;
    // we will increment the value and make everything right to it as 0
    last->data++;
    last = last->next;
    while (last != NULL) {
        last->data = 0;
        last = last->next;
    }
    return head;
}
int main()
{
    Node* head = new Node(1);
    head->next = new Node(9);
    head->next->next = new Node(9);
    head->next->next->next = new Node(9);
    head->next->next->next->next = new Node(9);

    head = addOneToList(head);
    printList(head);
    return 0;
}

class CarryOne{
 
    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 addOne(Node head)
    {
         
        Node last = null ;
        Node current_node = head;
        //Through this loop we will find the last non-nine node.
        while (current_node.next != null)
        {
            if (current_node.data != 9) {
                last = current_node;
            }
            current_node = current_node.next;
        }
        //This loop will run till the second last node, so for the last node we will check using if condition.
        //If the last node itself is not 9. Then simply increment the value by 1 and return the head.
        if (current_node.data != 9) {
            current_node.data=current_node.data+1;
            return head;
        }
        //After loop if last is still NULL, that means there is no value which is not 9.
        //For example 9->9->9->9
        if (last == null) {
            //1 extra node will be needed.
            last = newNode(1);
            last.next = head;
            head = last;
            //then make every node 0
            last = last.next;
            while (last != null) {
                last.data = 0;
                last = last.next;
            }
            return head;
        }
        //Last case => when the non-nine node is somewhere in middle;
        // we will increment the value and make everything right to it as 0
        last.data=last.data+1;
        last = last.next;
        while (last != null) {
            last.data = 0;
            last = last.next;
        }
        return head;
        
    }
     
    // A utility function to print a linked list
    static void printList(Node node)
    {
        while (node != null)
        {
            System.out.print(node.data);
            node = node.next;
        }
        System.out.println();
    }
     
    // Driver code
    public static void main(String[] args)
    {
        Node head = newNode(1);
        head.next = newNode(2);
        head.next.next = newNode(2);
     
        System.out.print("List is ");
        printList(head);
     
        head = addOne(head);
        System.out.println();
        System.out.print("Resultant list is ");
        printList(head);
    }
    }

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

def newNode(data):
	return Node(data)

def printList(head):
	if not head:
		return
	while(head):
		print("{}".format(head.data), end=" ")
		head = head.next

def addOneToList(head):
	last = None
	current_node = head

	# Through this loop we will find the last non-nine node
	while current_node.next:

		if current_node.data != 9:
			last = current_node

		current_node = current_node.next

	# This loop will run till the second last node, so for the last node we will check using if condition.
	# If the last node itself is not 9. Then simply increment the value by 1 and return the head.
	if current_node.data != 9:
		current_data.data += 1
		return head

	# After loop if last is still NULL, that means there is no value which is not 9
	# For example 9->9->9->9
	if last == None:
		# 1 extra node will be needed.
		last = newNode(1)
		last.next = head
		head = last

		# then make every node 0
		last = last.next
		while last != None:
			last.data = 0
			last = last.next

		return head

	# Last case => when the non-nine node is somewhere in middle;
	# we will increment the value and make everything right to it as 0
	last.data += 1
	last = last.next
	while last:
		last.data = 0
		last = last.next
	return head


if __name__ == '__main__':
	head = newNode(1)
	head.next = newNode(9)
	head.next.next = newNode(9)
	head.next.next.next = newNode(9)
	head.next.next.next.next = newNode(9)
	head = addOneToList(head)
	printList(head)