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:
- Lista enlazada inversa dada. Por ejemplo, 1-> 9-> 9 -> 9 se convierte en 9-> 9 -> 9 ->1.
- 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.
- Invierta la lista enlazada modificada y devuelva el encabezado.
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program to add 1 to a
// linked list
#include <bits/stdc++.h>
using namespace std;
// Linked list node
class Node
{
public:
int data;
Node* next;
};
/* Function to create a new node
with given data */
Node *newNode(int data)
{
Node *new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// Function to reverse the linked list
Node *reverse(Node *head)
{
Node * prev = NULL;
Node * current = head;
Node * 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 */
Node *addOneUtil(Node *head)
{
// res is head node of the
// resultant list
Node* res = head;
Node *temp, *prev = NULL;
int 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().
Node* addOne(Node *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
void printList(Node *node)
{
while (node != NULL)
{
cout << node->data;
node = node->next;
}
cout<<endl;
}
// Driver code
int main(void)
{
Node *head = newNode(1);
head->next = newNode(9);
head->next->next = newNode(9);
head->next->next->next = newNode(9);
cout << "List is ";
printList(head);
head = addOne(head);
cout << "Resultant list is ";
printList(head);
return 0;
}
// This is code is contributed by rathbhupendra
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.
C++
// Recursive C++ program to add 1 to
// a linked list
#include <bits/stdc++.h>
// Linked list node
struct Node
{
int data;
Node* next;
};
/* Function to create a new
node with given data */
Node* newNode(int data)
{
Node* 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.
int addWithCarry(Node* head)
{
// If linked list is empty,
// then return carry
if (head == NULL)
return 1;
// Add carry returned be next
// node call
int res = head->data + addWithCarry(head->next);
// Update data and return new carry
head->data = (res) % 10;
return (res) / 10;
}
// This function mainly uses addWithCarry().
Node* addOne(Node* head)
{
// Add 1 to linked list from end
// to beginning
int carry = addWithCarry(head);
// If there is carry after processing
// all nodes, then we need to add a
// new node to linked list
if (carry)
{
Node* newNode = new Node;
newNode->data = carry;
newNode->next = head;
// New node becomes head now
return newNode;
}
return head;
}
// A utility function to print
// a linked list
void printList(Node* node)
{
while (node != NULL)
{
printf("%d", node->data);
node = node->next;
}
printf("");
}
// Driver code
int main(void)
{
Node* head = newNode(1);
head->next = newNode(9);
head->next->next = newNode(9);
head->next->next->next = newNode(9);
printf("List is ");
printList(head);
head = addOne(head);
printf("Resultant list is ");
printList(head);
return 0;
}
Producción:
List is 1999 Resultant list is 2000
Enfoque simple y fácil implementación: la idea es almacenar el último puntero que no sea de 9 dígitos para que, si el último puntero es cero, podamos reemplazar todos los Nodes después del Node almacenado (que contiene la ubicación del último dígito antes del 9) a 0 y agregar el valor del Node almacenado por 1
C++
// Recursive C++ program to add 1 to
// a linked list
#include <bits/stdc++.h>
// Linked list node
struct Node
{
int data;
Node* next;
};
/* Function to create a new
node with given data */
Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
Node* addOne(Node* head)
{
// Your Code here
// return head of list after
// adding one
Node* ln = head;
if (head->next == NULL)
{
head->data += 1;
return head;
}
Node* t = head;
int prev;
while (t->next)
{
if (t->data != 9)
{
ln = t;
}
t = t->next;
}
if (t->data == 9 &&
ln != NULL)
{
if (ln->data == 9 &&
ln == head)
{
Node* temp = newNode(1);
temp->next = head;
head = temp;
t = ln;
}
else
{
t = ln;
t->data += 1;
t = t->next;
}
while (t)
{
t->data = 0;
t = t->next;
}
}
else
{
t->data += 1;
}
return head;
}
// A utility function to print
// a linked list
void printList(Node* node)
{
while (node != NULL)
{
printf("%d->",
node->data);
node = node->next;
}
printf("NULL");
printf("");
}
// Driver code
int main(void)
{
Node* head = newNode(1);
head->next = newNode(9);
head->next->next = newNode(9);
head->next->next->next = newNode(9);
printf("List is ");
printList(head);
head = addOne(head);
printf("Resultant list is ");
printList(head);
return 0;
}
// This code is contribute bu maddler
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!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA