Javascript Program For Adding 1 To A Number Represented As Linked List

// Javascript program to add 1 to 
// a linked list 

// Linked list node 
class Node {
    constructor() {
        this.data = 0;
        this.next = null;
    }
};

/* Function to create a new node 
   with given data */
function newNode(data) {
    let new_node = new Node();
    new_node.data = data;
    new_node.next = null;
    return new_node;
}

// Function to reverse the 
// linked list 
function reverse(head) {
    let prev = null;
    let current = head;
    let next;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

/* Adds one to a linked lists and 
   return the head node of resultant 
   list */
function addOneUtil(head) {
    // res is head node of the 
    // resultant list 
    let res = head;
    let temp, prev = null;

    let carry = 1, sum;

    // while both lists exist 
    while (head != null) {
        // Calculate value of next digit in 
        // resultant list. The next digit is 
        // sum of following things 
        // (i) Carry 
        // (ii) Next digit of head list (if 
        // there is a next digit) 
        sum = carry + head.data;

        // update carry for next calculation 
        carry = (sum >= 10) ? 1 : 0;

        // update sum if it is greater than 10 
        sum = sum % 10;

        // Create a new node with sum as data 
        head.data = sum;

        // Move head and second pointers to 
        // next nodes 
        temp = head;
        head = head.next;
    }

    // if some carry is still there, add a 
    // new node to result list. 
    if (carry > 0)
        temp.next = newNode(carry);

    // return head of the resultant list 
    return res;
}

// This function mainly uses addOneUtil(). 
function addOne(head) {
    // Reverse linked list 
    head = reverse(head);

    // Add one from left to right of 
    // reversed list 
    head = addOneUtil(head);

    // Reverse the modified list 
    return reverse(head);
}

// A utility function to print a 
// linked list 
function printList(node) {
    while (node != null) {
        console.log(node.data);
        node = node.next;
    }
}

// Driver code
let head = newNode(1);
head.next = newNode(9);
head.next.next = newNode(9);
head.next.next.next = newNode(9);
console.log("List is ");
printList(head);
head = addOne(head);
console.log("Resultant list is ");
printList(head);
// This code is contributed by rrrtnx.

// Recursive JavaScript program
// to add 1 to a linked list
// Linked list node 
class Node {
    constructor() {
        this.data = 0;
        this.next = null;
    }
}

/* Function to create a new node 
   with given data */
function newNode(data) {
    let new_node = new Node();
    new_node.data = data;
    new_node.next = null;
    return new_node;
}

// Recursively add 1 from end to 
// beginning and returns carry after 
// all nodes are processed.
function addWithCarry(head) {
    // If linked list is empty, then
    // return carry
    if (head == null) return 1;

    // Add carry returned be next node 
    // call
    let res = head.data + addWithCarry(head.next);

    // Update data and return new carry
    head.data = res % 10;
    return parseInt(res / 10);
}

// This function mainly uses 
// addWithCarry().
function addOne(head) {
    // Add 1 to linked list from end  
    // to beginning
    let carry = addWithCarry(head);
    let newNodes = null;

    // If there is carry after processing 
    // all nodes, then we need to add a 
    // new node to linked list
    if (carry > 0) {
        newNodes = newNode(carry);
        newNodes.next = head;

        // New node becomes head now
        return newNodes;
    }

    return head;
}

// A utility function to print a 
// linked list
function printList(node) {
    while (node != null) {
        console.log(node.data);
        node = node.next;
    }
}

// Driver code 
let head = newNode(1);
head.next = newNode(9);
head.next.next = newNode(9);
head.next.next.next = newNode(9);

console.log("List is ");
printList(head);
head = addOne(head);
console.log("Resultant list is ");
printList(head);