9. Add 1 to a number represented as linked list

9. Add 1 to a number represented as linked list

Problem link :- click here

package Linked_List;

public class LinkedList__9
{

	/*
	 	input :   1-> 2-> 3-> null
	 	output : 1-> 2-> 4-> null
	 	
	 	We have to add 1 to the number, where number is the linked list so we have
	 	to add the number to the last node.
	 	this is quite easy, but if we get a carry then it is problem(as we are supposed
	 	to store only one digit in one node.
	 	
	 	To handle this case we will reverse the linked list first, 
	 	and then we will add the number to the head(as we have reversed head is
	 	the last node)
	 	and store the unit part of the sum to the head and tens part to the carry.
	 	
	 	we will add the carry to the next node until it becomes zero 
	 	
	 	lastly we have to reverse the linked list
	 */
	
	static void reverse(LinkedList list)
	{
		Node prev, cur, next;
		prev = null;
		cur = list.head;
		next = cur.next;
		
		while(cur!=null)
		{
			next = cur.next;
			
			cur.next = prev;
			
			prev = cur;
			cur = next;
		}
		list.head = prev;
	}
	
	static void addOneToLinkedList(LinkedList list, int to_add)
	{
		//step 1 :-
		reverse(list);
		
		//step 2:- We have to add 1 to the head
		Node temp = list.head;
		int sum = temp.data + to_add;
		
		list.head.data = sum%10;
		int carry = sum/10;
		
		//step 3:- If there is a carry then we have to add it to the next node
		while(carry != 0   &&   temp.next != null)
		{
			temp = temp.next;
			
			sum = temp.data + carry;
			temp.data = sum % 10;
			carry = sum/10;
		}
		
		//if there is no more node but carry is there then 
		//we have to add another node to the end
		while(carry != 0   &&   temp.next == null)
		{
			int data = carry % 10;
			Node node = new Node(data);
			temp.next = node;
			carry = carry/10;
			
			temp = temp.next;
		}
		
		//final step we have to reverse the linked list
		reverse(list);
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		
		int to_add = 19000;
		
		System.out.println("Linkrd list before adding : ");
		printList(list);
		
		addOneToLinkedList(list, to_add);
		System.out.println("Linked list after adding : ");
		printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)