Posted on Mar 9, 2021

Add 1 to the Number(Wrapped in linked List)

#algorithms #programming #discuss #javascript

Add one to the Number wrapped in LinkedList

(Benefits of LinkedList: no limits for a number)
Given a linked list denoting a number (each key will have numbers from 0-9), implement a function for adding 1 to it.
Example - For number 7899, Linked List would be [7, 8, 9, 9]
If you add 1 to 7899, you get 7900 which is [7, 9, 0, 0]

Input1: [7, 8, 9, 9] Output1: [7, 9, 0, 0]

My Approach:

The idea is to solve the problem by the backtracking technique.
As when we add the multi-digit number, we start from the end. Thus, carrying a borrow from last to first digit we get our answer. I will follow the same approach in my code.

CODE:

//function converting nums in linkedList function getLinkedList ( ...arr ) { let nodesArray = []; for( var index=0; index<arr.length; index++ ) { nodesArray.push({ digit: arr[index], next:null }) } for( var index = 0; index < nodesArray.length-1; index++ ) { nodesArray[index].next = nodesArray[index+1]; } if(nodesArray.length){ return nodesArray[0]; } } //prints the linkedList's digits in an Array. function printList(list) { let arr = [], node = list; while(node != null) { arr.push(node.digit); node = node.next; } console.log(arr); } let list = getLinkedList(7, 8, 9, 9); printList(list); // [7, 8, 9, 9] let num =1;//number to be added //function which will add one to the number function addOne(_list) { //to achieve backtracking calling function before implementation till end if(_list.next != undefined){ addOne(_list.next); } _list.digit += num; //borrow will be in case of sum 10 or greater than ten if(_list.digit>10){ _list.digit = 10-_list.digit; num = 1; } else if(_list.digit=== 10){ _list.digit = 0; num = 1; } else {////borrow will be zero when sum is less than 10 num =0; } //to handle all nine case,  //example in case of 9999, answer will be 10000 if(list === _list && num!= 0 ){ //creating new node for the last borrow (1), in case of all nine list = { digit : num, next: list } } } addOne(list); printList(list); // [7, 9, 0, 0] //in case of[9, 9, 9, 9], the output is [1,0,0,0,0]