Clonar una lista enlazada con el puntero siguiente y aleatorio

Un ejemplo de lista enlazada con un puntero aleatorio Dada una lista enlazada de tamaño N donde cada Node tiene dos enlaces: un puntero apunta al siguiente Node y el segundo apunta a cualquier Node en la lista. La tarea es crear un clon de esta lista enlazada en tiempo O(N) . 

Nota: El puntero que apunta al siguiente Node es el puntero ‘ siguiente ‘ y el que apunta a un Node arbitrario se llama puntero ‘arbit’ ya que puede apuntar a cualquier Node arbitrario en la lista enlazada. 

Un ejemplo de la lista enlazada se muestra en la siguiente imagen:

Ejemplo de lista enlazada con un puntero aleatorioEjemplo de lista enlazada con un puntero aleatorio

Enfoque 1 (usando espacio adicional): la idea para resolver este problema es: 

Primero cree una única lista vinculada con solo el puntero ‘siguiente’ y use una asignación para asignar los nuevos Nodes a sus Nodes correspondientes en la lista vinculada dada. Ahora use este mapeo para señalar el Node arbitrario desde cualquier Node en la lista recién creada. 

Siga los pasos mencionados amados para implementar la idea anterior:

• Cree un duplicado (digamos Y ) para cada Node (digamos X ) y mapéelos con los Nodes antiguos correspondientes (digamos mp , So mp[X] = Y ).
• Cree la lista enlazada única de los Nodes duplicados donde cada Node solo tiene el puntero ‘siguiente’ .
• Ahora itere sobre la lista enlazada antigua y haga lo siguiente:
  • Encuentre el Node duplicado asignado al actual. (es decir, si el Node actual es X entonces el duplicado es mp[x] )
  • Haga que el puntero de arbitraje del Node duplicado apunte al duplicado del actual-> Node de arbitraje (es decir, mp[x]->arbit apuntará a mp[X->arbit] ).
• La lista enlazada creada de esta manera es la lista enlazada requerida. 

Siga la ilustración a continuación para una mejor comprensión:

Ilustración:

Considere la lista enlazada que se muestra a continuación:

Lista enlazada original 

Los enlaces verdes son los punteros de arbitraje.

Creando una copia de Nodes y el siguiente puntero:

Inicialmente, cree una lista enlazada única de Nodes duplicados con solo los siguientes punteros y mapéelos con los antiguos. 
Aquí los enlaces de color azul se utilizan para mostrar el mapeo.

Nueva lista enlazada mapeada con Nodes antiguos

Vinculación de los punteros de arbitraje:

Ahora iterando la array anterior y actualizando los punteros de arbitraje como se menciona en el enfoque. Los enlaces de color verde son los punteros de arbitraje.

En el primer Node:

Puntero de arbitraje de enlace del duplicado del primer Node

En el Node sconde:

Puntero de arbitraje de enlace del duplicado del segundo Node

En el tercer Node:

Puntero de arbitraje de enlace del duplicado del tercer Node

En el cuarto Node:

Puntero de arbitraje de enlace del duplicado del cuarto Node

En el quinto Node:

Puntero de arbitraje de enlace del duplicado del quinto Node

La lista enlazada final es como se muestra a continuación:

El original y el clon.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node of linked list
struct Node {
    int val;
    Node* next;
    Node* arbit;
   
    // Constructor
    Node(int x)
    {
        this->val = x;
        this->next = NULL;
        this->arbit = NULL;
    }
};
 
// Function to clone the linked list
Node* cloneLinkedList(Node* head)
{
    // Map to store the mapping of
    // old nodes with new ones
    unordered_map<Node*, Node*> mp;
    Node *temp, *nhead;
   
    // Duplicate of the first node
    temp = head;
    nhead = new Node(temp->val);
    mp[temp] = nhead;
   
    // Loop to create duplicates of nodes
    // with only next pointer
    while (temp->next != NULL) {
        nhead->next
            = new Node(temp->next->val);
        temp = temp->next;
        nhead = nhead->next;
        mp[temp] = nhead;
    }
    temp = head;
   
    // Loop to clone the arbit pointers
    while (temp != NULL) {
        mp[temp]->arbit = mp[temp->arbit];
        temp = temp->next;
    }
   
    // Return the head of the clone
    return mp[head];
}
 
// Function to print the linked list
void printList(Node* head)
{
    cout << head->val << "("
         << head->arbit->val << ")";
    head = head->next;
    while (head != NULL) {
        cout << " -> " << head->val << "("
             << head->arbit->val << ")";
        head = head->next;
    }
    cout << endl;
}
 
// Driver code
int main()
{
    // Creating a linked list with random pointer
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next
        = new Node(5);
    head->arbit = head->next->next;
    head->next->arbit = head;
    head->next->next->arbit
        = head->next->next->next->next;
    head->next->next->next->arbit
        = head->next->next;
    head->next->next->next->next->arbit
        = head->next;
   
    // Print the original list
    cout << "The original linked list:\n";
    printList(head);
   
    // Function call
    Node* sol = cloneLinkedList(head);
   
    cout << "The cloned linked list:\n";
    printList(sol);
   
    return 0;
}

Complejidad temporal:  O(N) 
Espacio auxiliar:  O(N) 

Enfoque 2 (usando espacio adicional constante):   la idea para resolver es usar espacio adicional constante es:

Cree un duplicado de un Node e insértelo entre ese Node y el Node justo al lado. 

Ahora, para un Node X , su duplicado será X->next y el puntero arbitrario del duplicado apuntará a X->arbit->next [ya que ese es el duplicado de X->arbit ]

Siga los pasos mencionados a continuación para implementar la idea:

• Cree la copia del Node 1 e insértela entre el Node 1 y el Node 2 en la lista enlazada original, cree la copia del Node 2 e insértela entre el 2º ^y el 3er ^Node y así sucesivamente. Agregue la copia de N después del Node N. 
• Ahora copie el enlace arbitrario de esta manera:

original->siguiente->arbitrario = original->arbitrario->siguiente 

• Ahora restaure las listas enlazadas originales y copie de esta manera en un solo ciclo. 

original->siguiente = original->siguiente->siguiente;
copiar->siguiente = copiar->siguiente->siguiente;

• Asegúrese de que el último elemento de original->next sea NULL. 

Consulte la publicación a continuación para la implementación de este método. 
Clona una lista enlazada con el puntero siguiente y aleatorio en el espacio O(1) 
Complejidad del tiempo: O(N) 
Espacio auxiliar: O(1) 

Gracias a Saravanan Mani por brindar esta solución. Esta solución funciona usando espacio constante.

Artículo relacionado:  
Clonar una lista enlazada con puntero siguiente y aleatorio | conjunto 2