Dados dos números representados por dos listas enlazadas, escriba una función que devuelva lista suma. La lista de suma es una representación de lista enlazada de la suma de dos números de entrada. Complejidad espacial esperada O(1).
Ejemplos:
Entrada:
L1 = 5 -> 6 -> 3 -> NULO
L2 = 8 -> 4 -> 2 -> NULO
Salida: 1 -> 4 -> 0 -> 5 -> NULOEntrada:
L1 = 1 -> 0 -> 0 -> NULO
L2 = 9 -> 1 -> NULO
Salida: 1 -> 9 -> 1 -> NULO
Enfoque: aquí hemos discutido una solución en la que usamos la recursividad para llegar al número menos significativo en las listas, pero debido a la participación de la pila, la complejidad espacial de la solución se convierte en O (N)
Aquí el objetivo es hacer el sum inplace y devolver la lista de suma modificada.
La idea es invertir primero la lista vinculada, de modo que el nuevo encabezado de la lista apunte al número menos significativo y podamos comenzar a agregar como se describe aquí y, en lugar de crear una nueva lista, modificamos la existente y devolvemos el encabezado de la lista modificada. .
Los siguientes son los pasos:
- Lista inversa L1.
- Lista inversa L2.
- Agregue los Nodes de ambas listas de forma iterativa.
- Invierta la lista resultante y devuelva su cabeza.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
class LinkedList;
// Node class for the linked list
class Node {
int data;
Node* next;
friend LinkedList;
public:
Node();
Node(int x);
};
Node::Node()
{
data = 0;
next = NULL;
}
// Function to initialise
// a node with value x
Node::Node(int x)
{
data = x;
next = NULL;
}
// Linkedlist class with helper functions
class LinkedList {
public:
Node* head;
LinkedList();
void insert(int x);
void reverse();
void traverse();
void sum(LinkedList*);
};
LinkedList::LinkedList()
{
head = NULL;
}
// Function to insert a node at
// the head of the list
void LinkedList::insert(int x)
{
Node* node = new Node();
node->data = x;
if (head == NULL)
head = node;
else {
node->next = head;
head = node;
}
}
// Function to reverse the linked list
void LinkedList::reverse()
{
Node *prev = NULL, *curr = head;
while (curr) {
Node* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
head = prev;
}
// Function to traverse and print the list
void LinkedList::traverse()
{
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL";
}
// Function to add two numbers
// represented as linked lists
void LinkedList::sum(LinkedList* l2)
{
reverse();
l2->reverse();
Node *start1 = head, *start2 = l2->head;
Node* prev = NULL;
int carry = 0;
// While both lists exist
while (start1 && start2) {
// Current sum
int temp = start1->data + start2->data + carry;
// Handle carry
start1->data = temp % 10;
carry = temp / 10;
prev = start1;
// Get to next nodes
start1 = start1->next;
start2 = start2->next;
}
// If there are remaining digits
// in any one of the lists
if (start1 || start2) {
if (start2)
prev->next = start2;
start1 = prev->next;
// While first list has digits remaining
while (start1) {
int temp = start1->data + carry;
start1->data = temp % 10;
carry = temp / 10;
prev = start1;
start1 = start1->next;
}
}
// If a new node needs to be
// created due to carry
if (carry > 0) {
prev->next = new Node(carry);
}
// Reverse the resultant list
reverse();
}
// Driver code
int main()
{
// Create first list
LinkedList* l1 = new LinkedList();
l1->insert(3);
l1->insert(6);
l1->insert(5);
// Create second list
LinkedList* l2 = new LinkedList();
l2->insert(2);
l2->insert(4);
l2->insert(8);
// Add the lists
l1->sum(l2);
// Print the resultant list
l1->traverse();
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class Node
{
int data;
Node next;
// constructor
Node(int d)
{
data = d;
next = null;
}
}// Node closes
class LinkedList
{
Node head;
// Helper function to traverse
void traverse(Node head)
{
while(head != null)
{
System.out.print(head.data + "->");
head = head.next;
}
}
// Helper function to insert data in linked list
void insert(int x)
{
Node temp = new Node(x);
if(head == null) head = temp;
else
{
temp.next = head;
head = temp;
}
}
// Helper function to reverse the list
public static Node reverse(Node head)
{
if(head == null || head.next == null) return head;
Node prev = null;
Node curr = head;
while(curr != null)
{
Node temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head = prev;
return head;
}
// Function to add two lists
public static Node sum(Node l1, Node l2)
{
if(l2 == null) return l1;
if(l1 == null) return l2;
// reverse l1 list
l1 = reverse(l1);
// reverse l2 list
l2 = reverse(l2);
// storing head whose reverse is to be returned
// This is where which will be final node
Node head = l1;
Node prev = null;
int c = 0,sum;
while(l1 != null && l2 != null)
{
sum = c + l1.data + l2.data;
l1.data = sum % 10;
c = sum / 10;
prev = l1;
l1 = l1.next;
l2 = l2.next;
}
if(l1 != null||l2 != null)
{
if(l2 != null) prev.next = l2;
l1 = prev.next;
while(l1 != null)
{
sum = c + l1.data;
l1.data = sum % 10;
c = sum / 10;
prev = l1;
l1 = l1.next;
}
}
if(c > 0) prev.next = new Node(c);
return reverse(head);
}
// Driver Code
public static void main(String[] args)
{
LinkedList l1 = new LinkedList();
l1.insert(3);
l1.insert(6);
l1.insert(5);
LinkedList l2 = new LinkedList();
l2.insert(2);
l2.insert(4);
l2.insert(8);
LinkedList l3 = new LinkedList();
Node head = sum(l1.head, l2.head);
l3.traverse(head);
System.out.print("Null");
}
}
// This code is contributed
// by Devarshi Singh
Python3
# Python3 implementation of the approach # Linked List Node class Node: def __init__(self, data): self.data = data self.next = None # Handle list operations class LinkedList: def __init__(self): self.head = None # Method to traverse list and # return it in a format def traverse(self): linkedListStr = "" temp = self.head while temp: linkedListStr += str(temp.data) + " -> " temp = temp.next return linkedListStr + "NULL" # Method to insert data in linked list def insert(self, data): newNode = Node(data) if self.head is None: self.head = newNode else: newNode.next = self.head self.head = newNode # Helper function to reverse the list def reverse(Head): if (Head is None and Head.next is None): return Head prev = None curr = Head while curr: temp = curr.next curr.next = prev prev = curr curr = temp Head = prev return Head # Function to add two lists def listSum(l1, l2): if l1 is None: return l1 if l2 is None: return l2 # Reverse first list l1 = reverse(l1) # Reverse second list l2 = reverse(l2) # Storing head whose reverse # is to be returned This is # where which will be final node head = l1 prev = None c = 0 sum = 0 while l1 is not None and l2 is not None: sum = c + l1.data + l2.data l1.data = sum % 10 c = int(sum / 10) prev = l1 l1 = l1.next l2 = l2.next if l1 is not None or l2 is not None: if l2 is not None: prev.next = l2 l1 = prev.next while l1 is not None: sum = c + l1.data l1.data = sum % 10 c = int(sum / 10) prev = l1 l1 = l1.next if c > 0: prev.next = Node(c) return reverse(head) # Driver code linkedList1 = LinkedList() linkedList1.insert(3) linkedList1.insert(6) linkedList1.insert(5) linkedList2 = LinkedList() linkedList2.insert(2) linkedList2.insert(4) linkedList2.insert(8) linkedList3 = LinkedList() linkedList3.head = listSum(linkedList1.head, linkedList2.head) print(linkedList3.traverse()) # This code is contributed by Debidutta Rath
C#
// C# implementation of the above approach
using System;
public class Node
{
public int data;
public Node next;
// constructor
public Node(int d)
{
data = d;
next = null;
}
}
// Node closes
public class LinkedList
{
Node head;
// Helper function to traverse
void traverse(Node head)
{
while(head != null)
{
Console.Write(head.data + "->");
head = head.next;
}
}
// Helper function to insert data in linked list
void insert(int x)
{
Node temp = new Node(x);
if(head == null) head = temp;
else
{
temp.next = head;
head = temp;
}
}
// Helper function to reverse the list
public static Node reverse(Node head)
{
if(head == null ||
head.next == null) return head;
Node prev = null;
Node curr = head;
while(curr != null)
{
Node temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
head = prev;
return head;
}
// Function to add two lists
public static Node sum(Node l1, Node l2)
{
if(l2 == null) return l1;
if(l1 == null) return l2;
// reverse l1 list
l1 = reverse(l1);
// reverse l2 list
l2 = reverse(l2);
// storing head whose reverse is
// to be returned. This is where
// which will be final node
Node head = l1;
Node prev = null;
int c = 0,sum;
while(l1 != null && l2 != null)
{
sum = c + l1.data + l2.data;
l1.data = sum % 10;
c = sum / 10;
prev = l1;
l1 = l1.next;
l2 = l2.next;
}
if(l1 != null||l2 != null)
{
if(l2 != null) prev.next = l2;
l1 = prev.next;
while(l1 != null)
{
sum = c + l1.data;
l1.data = sum % 10;
c = sum / 10;
prev = l1;
l1 = l1.next;
}
}
if(c > 0) prev.next = new Node(c);
return reverse(head);
}
// Driver Code
public static void Main(String[] args)
{
LinkedList l1 = new LinkedList();
l1.insert(3);
l1.insert(6);
l1.insert(5);
LinkedList l2 = new LinkedList();
l2.insert(2);
l2.insert(4);
l2.insert(8);
LinkedList l3 = new LinkedList();
Node head = sum(l1.head, l2.head);
l3.traverse(head);
Console.Write("Null");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
// Linkedlist class with helper functions
class LinkedList {
constructor()
{
this.head = null;
}
// Function to insert a node at
// the head of the list
insert(x)
{
var node = new Node();
node.data = x;
if (this.head == null)
this.head = node;
else {
node.next = this.head;
this.head = node;
}
}
// Function to reverse the linked list
reverse()
{
var prev = null, curr = this.head;
while (curr) {
var temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
this.head = prev;
}
// Function to traverse and print the list
traverse()
{
var temp = this.head;
while (temp) {
document.write( temp.data + " -> ");
temp = temp.next;
}
document.write( "null");
}
// Function to add two numbers
// represented as linked lists
sum(l2)
{
this.reverse();
l2.reverse();
var start1 = this.head, start2 = l2.head;
var prev = null;
var carry = 0;
// While both lists exist
while (start1 && start2) {
// Current sum
var temp = start1.data + start2.data + carry;
// Handle carry
start1.data = temp % 10;
carry = parseInt(temp / 10);
prev = start1;
// Get to next nodes
start1 = start1.next;
start2 = start2.next;
}
// If there are remaining digits
// in any one of the lists
if (start1 || start2) {
if (start2)
prev.next = start2;
start1 = prev.next;
// While first list has digits remaining
while (start1) {
var temp = start1.data + carry;
start1.data = temp % 10;
carry = parseInt(temp / 10);
prev = start1;
start1 = start1.next;
}
}
// If a new node needs to be
// created due to carry
if (carry > 0) {
prev.next = new Node(carry);
}
// Reverse the resultant list
this.reverse();
}
};
// Driver code
// Create first list
var l1 = new LinkedList();
l1.insert(3);
l1.insert(6);
l1.insert(5);
// Create second list
var l2 = new LinkedList();
l2.insert(2);
l2.insert(4);
l2.insert(8);
// Add the lists
l1.sum(l2);
// Print the resultant list
l1.traverse();
// This code is contributed by itsok.
</script>
Producción:
1 -> 4 -> 0 -> 5 -> NULL
Complejidad de tiempo: O(max(m, n)) donde m y n son el número de Nodes en la lista l1 y la lista l2 respectivamente.
Complejidad espacial: O(1)
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