Add One to Linked List Problem

Given a natural number in the form of a linked list, add 1 to it.

Asked by Amazon

Examples

Linked List: 7→8→9
Resultant List: 7→9→0

Linked List: 9→9→9
Resultant List: 1→0→0→0

Approach

store all the element into a stack = [9,9,9]

take a carry variable default value = 1

pop the element from the stack, add 1 into the element value

if the current value is 9 then we have to make current value = 0 and carry = 1

else increase the current value by 1 and mark the carry = 0

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode addOneToList(ListNode head) {
		// add your logic here
		Stack<ListNode> stack = new Stack<>();
		ListNode temp = head;
		
		// push element into stack = [9,9,9]
		
		while(temp!=null){
			stack.push(temp);
			temp = temp.next;
		}
		
		int carry = 1;
		
		while(stack.size()>0){
			ListNode node = stack.pop();
			if(carry==1){
				if(node.data==9){
					node.data = 0;
				}else{
					node.data = node.data + 1;
					carry = 0;
				}
			}
		}
		if(carry==1){
			ListNode node = new ListNode(1);
			node.next = head;
			head = node;
		}
		return head;
		
	}
}