Dada una lista enlazada que tiene dos punteros en cada Node. El primero apunta al siguiente Node de la lista, sin embargo, el otro puntero es aleatorio y puede apuntar a cualquier Node de la lista. Escriba un programa que clone la lista dada en el espacio O(1), es decir, sin ningún espacio adicional.
Ejemplos:
Input : Head of the below-linked list
Output : A new linked list identical to the original list.
En las publicaciones anteriores, Set-1 y Set-2 se analizan varios métodos, y también está disponible la implementación de la complejidad del espacio O(n).
En esta publicación, implementaremos un algoritmo que no requerirá espacio adicional, como se explicó en el Conjunto 1.
A continuación se muestra el algoritmo:
- Cree la copia del Node 1 e insértela entre el Node 1 y el Node 2 en la lista enlazada original, cree una copia del 2 e insértela entre el 2 y el 3. Continúe de esta manera, agregue la copia de N después del enésimo Node
- Ahora copie el enlace aleatorio de esta manera
original->next->random= original->random->next; /*TRAVERSE TWO NODES*/
- Esto funciona porque original->siguiente no es más que una copia del original y Original->aleatorio->siguiente no es más que una copia del azar.
- Ahora restaure las listas enlazadas originales y copie de esta manera en un solo ciclo.
original->next = original->next->next;
copy->next = copy->next->next;
- Asegúrese de que original->next sea NULL y devuelva la lista clonada
A continuación se muestra la implementación.
C++
// C++ program to clone a linked list with next
// and arbit pointers in O(n) time
#include <bits/stdc++.h>
using namespace std;
// Structure of linked list Node
struct Node
{
int data;
Node *next,*random;
Node(int x)
{
data = x;
next = random = NULL;
}
};
// Utility function to print the list.
void print(Node *start)
{
Node *ptr = start;
while (ptr)
{
cout << "Data = " << ptr->data << ", Random = "
<< ptr->random->data << endl;
ptr = ptr->next;
}
}
// This function clones a given linked list
// in O(1) space
Node* clone(Node *start)
{
Node* curr = start, *temp;
// insert additional node after
// every node of original list
while (curr)
{
temp = curr->next;
// Inserting node
curr->next = new Node(curr->data);
curr->next->next = temp;
curr = temp;
}
curr = start;
// adjust the random pointers of the
// newly added nodes
while (curr)
{
if(curr->next)
curr->next->random = curr->random ?
curr->random->next : curr->random;
// move to the next newly added node by
// skipping an original node
curr = curr->next?curr->next->next:curr->next;
}
Node* original = start, *copy = start->next;
// save the start of copied linked list
temp = copy;
// now separate the original list and copied list
while (original && copy)
{
original->next =
original->next? original->next->next : original->next;
copy->next = copy->next?copy->next->next:copy->next;
original = original->next;
copy = copy->next;
}
return temp;
}
// Driver code
int main()
{
Node* start = new Node(1);
start->next = new Node(2);
start->next->next = new Node(3);
start->next->next->next = new Node(4);
start->next->next->next->next = new Node(5);
// 1's random points to 3
start->random = start->next->next;
// 2's random points to 1
start->next->random = start;
// 3's and 4's random points to 5
start->next->next->random =
start->next->next->next->next;
start->next->next->next->random =
start->next->next->next->next;
// 5's random points to 2
start->next->next->next->next->random =
start->next;
cout << "Original list : \n";
print(start);
cout << "\nCloned list : \n";
Node *cloned_list = clone(start);
print(cloned_list);
return 0;
}
Java
// Java program to clone a linked list with next
// and arbit pointers in O(n) time
class GfG {
// Structure of linked list Node
static class Node {
int data;
Node next, random;
Node(int x)
{
data = x;
next = random = null;
}
}
// Utility function to print the list.
static void print(Node start)
{
Node ptr = start;
while (ptr != null) {
System.out.println("Data = " + ptr.data
+ ", Random = "
+ ptr.random.data);
ptr = ptr.next;
}
}
// This function clones a given
// linked list in O(1) space
static Node clone(Node start)
{
Node curr = start, temp = null;
// insert additional node after
// every node of original list
while (curr != null) {
temp = curr.next;
// Inserting node
curr.next = new Node(curr.data);
curr.next.next = temp;
curr = temp;
}
curr = start;
// adjust the random pointers of the
// newly added nodes
while (curr != null) {
if (curr.next != null)
curr.next.random = (curr.random != null)
? curr.random.next
: curr.random;
// move to the next newly added node by
// skipping an original node
curr = curr.next.next;
}
Node original = start, copy = start.next;
// save the start of copied linked list
temp = copy;
// now separate the original list and copied list
while (original != null) {
original.next =original.next.next;
copy.next = (copy.next != null) ? copy.next.next
: copy.next;
original = original.next;
copy = copy.next;
}
return temp;
}
// Driver code
public static void main(String[] args)
{
Node start = new Node(1);
start.next = new Node(2);
start.next.next = new Node(3);
start.next.next.next = new Node(4);
start.next.next.next.next = new Node(5);
// 1's random points to 3
start.random = start.next.next;
// 2's random points to 1
start.next.random = start;
// 3's and 4's random points to 5
start.next.next.random = start.next.next.next.next;
start.next.next.next.random
= start.next.next.next.next;
// 5's random points to 2
start.next.next.next.next.random = start.next;
System.out.println("Original list : ");
print(start);
System.out.println("Cloned list : ");
Node cloned_list = clone(start);
print(cloned_list);
}
}
// This code is contributed by Prerna Saini.
C#
// C# program to clone a linked list with
// next and arbit pointers in O(n) time
using System;
class GFG
{
// Structure of linked list Node
class Node
{
public int data;
public Node next, random;
public Node(int x)
{
data = x;
next = random = null;
}
}
// Utility function to print the list.
static void print(Node start)
{
Node ptr = start;
while (ptr != null)
{
Console.WriteLine("Data = " + ptr.data +
", Random = " +
ptr.random.data);
ptr = ptr.next;
}
}
// This function clones a given
// linked list in O(1) space
static Node clone(Node start)
{
Node curr = start, temp = null;
// insert additional node after
// every node of original list
while (curr != null)
{
temp = curr.next;
// Inserting node
curr.next = new Node(curr.data);
curr.next.next = temp;
curr = temp;
}
curr = start;
// adjust the random pointers of
// the newly added nodes
while (curr != null)
{
if(curr.next != null)
curr.next.random = (curr.random != null)
? curr.random.next : curr.random;
// move to the next newly added node
// by skipping an original node
curr = (curr.next != null) ? curr.next.next
: curr.next;
}
Node original = start, copy = start.next;
// save the start of copied linked list
temp = copy;
// now separate the original list
// and copied list
while (original != null && copy != null)
{
original.next = (original.next != null)?
original.next.next : original.next;
copy.next = (copy.next != null) ? copy.next.next
: copy.next;
original = original.next;
copy = copy.next;
}
return temp;
}
// Driver code
public static void Main(String[] args)
{
Node start = new Node(1);
start.next = new Node(2);
start.next.next = new Node(3);
start.next.next.next = new Node(4);
start.next.next.next.next = new Node(5);
// 1's random points to 3
start.random = start.next.next;
// 2's random points to 1
start.next.random = start;
// 3's and 4's random points to 5
start.next.next.random = start.next.next.next.next;
start.next.next.next.random = start.next.next.next.next;
// 5's random points to 2
start.next.next.next.next.random = start.next;
Console.WriteLine("Original list : ");
print(start);
Console.WriteLine("Cloned list : ");
Node cloned_list = clone(start);
print(cloned_list);
}
}
// This code has been contributed
// by Rajput-Ji
Python
'''Python program to clone a linked list with next and arbitrary pointers'''
'''Done in O(n) time with O(1) extra space'''
class Node:
'''Structure of linked list node'''
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def clone(original_root):
'''Clone a doubly linked list with random pointer'''
'''with O(1) extra space'''
'''Insert additional node after every node of original list'''
curr = original_root
while curr != None:
new = Node(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
'''Adjust the random pointers of the newly added nodes'''
curr = original_root
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
'''Detach original and duplicate list from each other'''
curr = original_root
dup_root = original_root.next
while curr.next != None:
tmp = curr.next
curr.next = curr.next.next
curr = tmp
return dup_root
def print_dlist(root):
'''Function to print the doubly linked list'''
curr = root
while curr != None:
print('Data =', curr.data, ', Random =', curr.random.data)
curr = curr.next
####### Driver code #######
'''Create a doubly linked list'''
original_list = Node(1)
original_list.next = Node(2)
original_list.next.next = Node(3)
original_list.next.next.next = Node(4)
original_list.next.next.next.next = Node(5)
'''Set the random pointers'''
# 1's random points to 3
original_list.random = original_list.next.next
# 2's random points to 1
original_list.next.random = original_list
# 3's random points to 5
original_list.next.next.random = original_list.next.next.next.next
# 4's random points to 5
original_list.next.next.next.random = original_list.next.next.next.next
# 5's random points to 2
original_list.next.next.next.next.random = original_list.next
'''Print the original linked list'''
print('Original list:')
print_dlist(original_list)
'''Create a duplicate linked list'''
cloned_list = clone(original_list)
'''Print the duplicate linked list'''
print('\nCloned list:')
print_dlist(cloned_list)
'''This code is contributed by Shashank Singh'''
Javascript
<script>
// Javascript program to clone a linked list with next
// and arbit pointers in O(n) time
// Structure of linked list Node
class Node {
constructor(x) {
this.data = x;
this.next = this.random = null;
}
}
// Utility function to print the list.
function print(start) {
var ptr = start;
while (ptr != null) {
document.write(
"Data = " +
ptr.data + ", Random = "
+ ptr.random.data+"<br/>"
);
ptr = ptr.next;
}
}
// This function clones a given
// linked list in O(1) space
function clone(start) {
var curr = start, temp = null;
// insert additional node after
// every node of original list
while (curr != null) {
temp = curr.next;
// Inserting node
curr.next = new Node(curr.data);
curr.next.next = temp;
curr = temp;
}
curr = start;
// adjust the random pointers of the
// newly added nodes
while (curr != null) {
if (curr.next != null)
curr.next.random = (curr.random != null) ?
curr.random.next : curr.random;
// move to the next newly added node by
// skipping an original node
curr = (curr.next != null) ?
curr.next.next : curr.next;
}
var original = start, copy = start.next;
// save the start of copied linked list
temp = copy;
// now separate the original list and copied list
while (original != null && copy != null) {
original.next = (original.next != null) ?
original.next.next : original.next;
copy.next = (copy.next != null) ?
copy.next.next : copy.next;
original = original.next;
copy = copy.next;
}
return temp;
}
// Driver code
var start = new Node(1);
start.next = new Node(2);
start.next.next = new Node(3);
start.next.next.next = new Node(4);
start.next.next.next.next = new Node(5);
// 1's random points to 3
start.random = start.next.next;
// 2's random points to 1
start.next.random = start;
// 3's and 4's random points to 5
start.next.next.random =
start.next.next.next.next;
start.next.next.next.random =
start.next.next.next.next;
// 5's random points to 2
start.next.next.next.next.random =
start.next;
document.write("Original list : <br/>");
print(start);
document.write("<br>");
document.write("Cloned list : <br/>");
var cloned_list = clone(start);
print(cloned_list);
// This code contributed by aashish1995
</script>
Producción
Original list : Data = 1, Random = 3 Data = 2, Random = 1 Data = 3, Random = 5 Data = 4, Random = 5 Data = 5, Random = 2 Cloned list : Data = 1, Random = 3 Data = 2, Random = 1 Data = 3, Random = 5 Data = 4, Random = 5 Data = 5, Random = 2
Complejidad de tiempo: O(n) Como nos movemos a través de la lista dos veces, es decir, 2n, pero en notaciones asintóticas eliminamos los términos constantes
Espacio auxiliar: O(1) Como no se usa espacio extra. Los n Nodes que se insertan entre los Nodes ya se requerían para clonar la lista, por lo que podemos decir que no usamos ningún espacio adicional.
Ashutosh Kumar contribuye con este artículo 😀 Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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