Dada una lista enlazada que representa un número entero donde cada Node es un dígito si el entero representado. La tarea es sumar un dígito dado N al entero representado.
Ejemplos:
Entrada: 9 -> 9 -> 3 -> NULO, N = 7
Salida:
9 -> 9 -> 3 -> NULO
1 -> 0 -> 0 -> 0 -> NULOEntrada: 2 -> 9 -> 9 -> NULO, N = 5
Salida:
2 -> 9 -> 9 -> NULO
3 -> 0 -> 4 -> NULO
Enfoque: Ya hemos discutido el enfoque para agregar 1 a un número almacenado en una lista vinculada en este artículo, pero el código requiere la inversión de la lista vinculada.
En esta publicación, hemos ampliado el problema para agregar cualquier dígito al número almacenado en una lista vinculada y lograr lo mismo sin reversión ni recurrencia.
La idea es recorrer la lista y, mientras se recorre, mantener un puntero al último Node cuyo valor sea menor que 9. Esto se debe a que estamos agregando un solo dígito al número almacenado en la lista vinculada. Entonces, el valor máximo de carry (si está presente) puede ser 1 . Supongamos que comenzamos a propagar el acarreo desde el dígito menos significativo hacia el dígito más significativo, luego la propagación se detendrá tan pronto como encuentre un número menor que 9.
Después del recorrido completo de la lista de esta manera, finalmente llegamos al último Node de la lista enlazada y también mantuvimos un puntero al último Node cuyo valor es menor que 9. Pueden
surgir dos casos:
- Puede haber un desbordamiento después de agregar el número en el último dígito, es decir, el valor en el Node es mayor que 9.
- Sin desbordamiento, es decir, después de agregar el valor en el Node es inferior a 10.
En el primer caso, tenemos que propagar el acarreo desde el último Node cuyo valor es menor que 9 hasta el último Node.
En el segundo caso, no tenemos que hacer nada más.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Node structure containing data
// and pointer to the next Node
struct node {
int key;
node* next;
node(int n)
{
key = n;
next = NULL;
}
};
// Linked list class
class LinkedList {
node* head;
public:
// Default constructor for
// creating empty list
LinkedList();
// Insert a node in linked list
void insert(node* n);
// Adding a single digit to the list
void addDigit(int n);
// Print the linked list
void printList();
};
LinkedList::LinkedList()
{
// Empty List
head = NULL;
}
// Function to insert a node at the
// head of the linked list
void LinkedList::insert(node* n)
{
// Empty List
if (head == NULL)
head = n;
// Insert in the beginning of the list
else {
n->next = head;
head = n;
}
}
// Function to print the linked list
void LinkedList::printList()
{
node* ptr = head;
while (ptr) {
cout << ptr->key << " -> ";
ptr = ptr->next;
}
cout << "NULL" << endl;
}
// Function to add a digit to the integer
// represented as a linked list
void LinkedList::addDigit(int n)
{
// To keep track of the last node
// whose value is less than 9
node* lastNode = NULL;
node* curr = head;
while (curr->next) {
// If found a node with value
// less than 9
if (curr->key < 9)
lastNode = curr;
// Otherwise keep traversing
// the list till end
curr = curr->next;
}
// Add the given digit to the last node
curr->key = curr->key + n;
// In case of overflow in the last node
if (curr->key > 9) {
curr->key = curr->key % 10;
// If the list is of the
// form 9 -> 9 -> 9 -> ...
if (lastNode == NULL) {
// Insert a node at the beginning as
// there would be overflow in the
// head in this case
insert(new node(1));
// Adjust the lastNode pointer to
// propagate the carry effect to
// all the nodes of the list
lastNode = head->next;
}
// Forward propagate carry effect
while (lastNode != curr) {
lastNode->key = (lastNode->key + 1) % 10;
lastNode = lastNode->next;
}
}
}
// Driver code
int main()
{
// Creating the linked list
LinkedList* l1 = new LinkedList();
// Adding elements to the linked list
l1->insert(new node(9));
l1->insert(new node(9));
l1->insert(new node(1));
// Printing the original list
l1->printList();
// Adding the digit
l1->addDigit(5);
// Printing the modified list
l1->printList();
return 0;
}
Java
// Java implementation of the approach
// Node structure containing data
// and pointer to the next Node
class node
{
int key;
node next;
node(int n)
{
key = n;
next = null;
}
};
// Linked list class
class LinkedList
{
static node head;
// Default constructor for
// creating empty list
public LinkedList()
{
// Empty List
head = null;
}
// Function to insert a node at the
// head of the linked list
void insert(node n)
{
// Empty List
if (head == null)
head = n;
// Insert in the beginning of the list
else
{
n.next = head;
head = n;
}
}
// Function to print the linked list
void printList()
{
node ptr = head;
while (ptr != null)
{
System.out.print(ptr.key + "->");
ptr = ptr.next;
}
System.out.print("null" + "\n");
}
// Function to add a digit to the integer
// represented as a linked list
void addDigit(int n)
{
// To keep track of the last node
// whose value is less than 9
node lastNode = null;
node curr = head;
while (curr.next != null)
{
// If found a node with value
// less than 9
if (curr.key < 9)
lastNode = curr;
// Otherwise keep traversing
// the list till end
curr = curr.next;
}
// Add the given digit to the last node
curr.key = curr.key + n;
// In case of overflow in the last node
if (curr.key > 9)
{
curr.key = curr.key % 10;
// If the list is of the
// form 9.9.9....
if (lastNode == null)
{
// Insert a node at the beginning as
// there would be overflow in the
// head in this case
insert(new node(1));
// Adjust the lastNode pointer to
// propagate the carry effect to
// all the nodes of the list
lastNode = head.next;
}
// Forward propagate carry effect
while (lastNode != curr)
{
lastNode.key = (lastNode.key + 1) % 10;
lastNode = lastNode.next;
}
}
}
// Driver code
public static void main(String[] args)
{
// Creating the linked list
LinkedList l1 = new LinkedList();
// Adding elements to the linked list
l1.insert(new node(9));
l1.insert(new node(9));
l1.insert(new node(1));
// Printing the original list
l1.printList();
// Adding the digit
l1.addDigit(5);
// Printing the modified list
l1.printList();
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
# Node structure containing data
# and pointer to the next Node
class node:
def __init__(self, key):
self.key = key
self.next = None
# Linked list class
class LinkedList:
def __init__(self):
self.head = None
# Function to insert a node at the
# head of the linked list
def insert(self, n):
# Empty List
if (self.head == None):
self.head = n
# Insert in the beginning of the list
else:
n.next = self.head;
self.head = n
# Function to print the linked list
def printList(self):
ptr = self.head
while (ptr != None):
print(ptr.key, end = ' -> ')
ptr = ptr.next
print('NULL')
# Function to add a digit to the integer
# represented as a linked list
def addDigit(self, n):
# To keep track of the last node
# whose value is less than 9
lastNode = None
curr = self.head
while (curr.next != None):
# If found a node with value
# less than 9
if (curr.key < 9):
lastNode = curr
# Otherwise keep traversing
# the list till end
curr = curr.next
# Add the given digit to the last node
curr.key = curr.key + n
# In case of overflow in the last node
if (curr.key > 9):
curr.key = curr.key % 10
# If the list is of the
# form 9 . 9 . 9 . ...
if (lastNode == None):
# Insert a node at the beginning as
# there would be overflow in the
# self.head in this case
self.insert(node(1))
# Adjust the lastNode pointer to
# propagate the carry effect to
# all the nodes of the list
lastNode = self.head.next
# Forward propagate carry effect
while (lastNode != curr):
lastNode.key = (lastNode.key + 1) % 10
lastNode = lastNode.next
# Driver code
if __name__=='__main__':
# Creating the linked list
l1 = LinkedList()
# Adding elements to the linked list
l1.insert(node(9))
l1.insert(node(9))
l1.insert(node(1))
# Printing the original list
l1.printList()
# Adding the digit
l1.addDigit(5)
# Printing the modified list
l1.printList()
# This code is contributed by rutvik_56
C#
// C# implementation of the approach
using System;
// Node structure containing data
// and pointer to the next Node
public class node
{
public int key;
public node next;
public node(int n)
{
key = n;
next = null;
}
};
// Linked list class
public class List
{
static node head;
// Default constructor for
// creating empty list
public List()
{
// Empty List
head = null;
}
// Function to insert a node at the
// head of the linked list
void insert(node n)
{
// Empty List
if (head == null)
head = n;
// Insert in the beginning of the list
else
{
n.next = head;
head = n;
}
}
// Function to print the linked list
void printList()
{
node ptr = head;
while (ptr != null)
{
Console.Write(ptr.key + "->");
ptr = ptr.next;
}
Console.Write("null" + "\n");
}
// Function to add a digit to the integer
// represented as a linked list
void addDigit(int n)
{
// To keep track of the last node
// whose value is less than 9
node lastNode = null;
node curr = head;
while (curr.next != null)
{
// If found a node with value
// less than 9
if (curr.key < 9)
lastNode = curr;
// Otherwise keep traversing
// the list till end
curr = curr.next;
}
// Add the given digit to the last node
curr.key = curr.key + n;
// In case of overflow in the last node
if (curr.key > 9)
{
curr.key = curr.key % 10;
// If the list is of the
// form 9.9.9....
if (lastNode == null)
{
// Insert a node at the beginning as
// there would be overflow in the
// head in this case
insert(new node(1));
// Adjust the lastNode pointer to
// propagate the carry effect to
// all the nodes of the list
lastNode = head.next;
}
// Forward propagate carry effect
while (lastNode != curr)
{
lastNode.key = (lastNode.key + 1) % 10;
lastNode = lastNode.next;
}
}
}
// Driver code
public static void Main(String[] args)
{
// Creating the linked list
List l1 = new List();
// Adding elements to the linked list
l1.insert(new node(9));
l1.insert(new node(9));
l1.insert(new node(1));
// Printing the original list
l1.printList();
// Adding the digit
l1.addDigit(5);
// Printing the modified list
l1.printList();
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Node structure containing data
// and pointer to the next Node
class node
{
constructor(n)
{
this.key = n;
this.next = null
}
};
// Linked list class
var head = null;
// Default constructor for
// creating empty list
function List()
{
// Empty List
head = null;
}
// Function to insert a node at the
// head of the linked list
function insert(n)
{
// Empty List
if (head == null)
head = n;
// Insert in the beginning of the list
else
{
n.next = head;
head = n;
}
}
// Function to print the linked list
function printList()
{
var ptr = head;
while (ptr != null)
{
document.write(ptr.key + " -> ");
ptr = ptr.next;
}
document.write("null" + "<br>");
}
// Function to add a digit to the integer
// represented as a linked list
function addDigit(n)
{
// To keep track of the last node
// whose value is less than 9
var lastNode = null;
var curr = head;
while (curr.next != null)
{
// If found a node with value
// less than 9
if (curr.key < 9)
lastNode = curr;
// Otherwise keep traversing
// the list till end
curr = curr.next;
}
// Add the given digit to the last node
curr.key = curr.key + n;
// In case of overflow in the last node
if (curr.key > 9)
{
curr.key = curr.key % 10;
// If the list is of the
// form 9.9.9....
if (lastNode == null)
{
// Insert a node at the beginning as
// there would be overflow in the
// head in this case
insert(new node(1));
// Adjust the lastNode pointer to
// propagate the carry effect to
// all the nodes of the list
lastNode = head.next;
}
// Forward propagate carry effect
while (lastNode != curr)
{
lastNode.key = (lastNode.key + 1) % 10;
lastNode = lastNode.next;
}
}
}
// Driver code
// Adding elements to the linked list
insert(new node(9));
insert(new node(9));
insert(new node(1));
// Printing the original list
printList();
// Adding the digit
addDigit(5);
// Printing the modified list
printList();
</script>
Producción:
1 -> 9 -> 9 -> NULL 2 -> 0 -> 4 -> NULL
Publicación traducida automáticamente
Artículo escrito por Ankur Goel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA