Programa Javascript para agregar 1 a un número representado como lista vinculada

El número se representa en la lista enlazada de modo que cada dígito corresponde a un Node en la lista enlazada. Súmale 1. Por ejemplo, 1999 se representa como (1-> 9-> 9 -> 9) y agregarle 1 debería cambiarlo a (2->0->0->0) 

A continuación se muestran los pasos: 

1. Lista enlazada inversa dada. Por ejemplo, 1-> 9-> 9 -> 9 se convierte en 9-> 9 -> 9 ->1.
2. Comience a recorrer la lista enlazada desde el Node más a la izquierda y agréguele 1. Si hay un acarreo, pasa al siguiente Node. Continúe moviéndose al siguiente Node mientras haya un acarreo.
3. Invierta la lista enlazada modificada y devuelva el encabezado.

A continuación se muestra la implementación de los pasos anteriores. 

<script>
// 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) 
{ 
    var new_node = new Node(); 
    new_node.data = data; 
    new_node.next = null; 
    return new_node; 
} 
  
// Function to reverse the 
// linked list 
function reverse(head) 
{ 
    var prev = null; 
    var current = head; 
    var 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 
    var res = head; 
    var temp, prev = null; 
  
    var 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) 
    { 
        document.write(node.data); 
        node = node.next; 
    } 
    document.write("<br>");
} 
  
// Driver code
var head = newNode(1); 
head.next = newNode(9); 
head.next.next = newNode(9); 
head.next.next.next = newNode(9); 
document.write( "List is "); 
printList(head); 
head = addOne(head); 
document.write("<br>Resultant list is "); 
printList(head); 
// This code is contributed by rrrtnx.
</script>

Producción:

List is 1999
Resultant list is 2000

Implementación recursiva: 
podemos llegar recursivamente al último Node y reenviar el transporte a los Nodes anteriores. La solución recursiva no requiere la inversión de la lista enlazada. También podemos usar una pila en lugar de recursividad para contener Nodes temporalmente.

A continuación se muestra la implementación de la solución recursiva.

<script>
// 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) 
{
    var 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
    var 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
    var carry = addWithCarry(head);
    var 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) 
    {
        document.write(node.data);
        node = node.next;
    }
    document.write("<br>");
}
  
// Driver code 
var head = newNode(1);
head.next = newNode(9);
head.next.next = newNode(9);
head.next.next.next = newNode(9);
  
document.write("List is ");
printList(head);
  
head = addOne(head);
document.write("<br>");
document.write("Resultant list is ");
printList(head);
</script>

Producción:

List is 1999
Resultant list is 2000

¡ Consulte el artículo completo sobre Agregar 1 a un número representado como una lista vinculada para obtener más detalles!