DEV Community

Cover image for Add 1 to the Number(Wrapped in linked List)
Aastha Talwaria
Aastha Talwaria

Posted on

Add 1 to the Number(Wrapped in linked List)

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]
Enter fullscreen mode Exit fullscreen mode

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] 
Enter fullscreen mode Exit fullscreen mode

Let's discuss your approach in the discussion box or you can hit me up at aastha.talwaria29@gmail.com.

Thanks for reading.

Top comments (0)