Clone a Linked List with Next and Random Pointer

Problem Statement

A linked list of length n is provided. Every node also has a random pointer that could refer to any node in the list or to null.

The list should be built as a deep copy (A copy of an object that does not share the same references as the source object from which it was copied is said to be a deep copy of that object). The deep copy should be made up of exactly n new nodes, each of which has the value set to that of the corresponding node from the original copy. The next and random pointer of the new nodes should point to new nodes in the copied list.

Example

Input:

Output:

Explanation: Copy of the linked list is being created with next and random pointers.

Input:

Output:

Explanation: Copy of the linked list is being created with next and random pointers.

Constraints

1<=length of linked list<=10000ts
1<=Data of Node<=1000

Approach 1 – Uses O(n) Extra Space

To clone a linked list with next and random pointer, This approach first saves the next and arbitrary pointers (from the original list) in an array before making a copy of the original Linked List.

• Go over the original linked list and create a data duplicate of it.
• Make an array containing the next and random pointer values for each node of the original linked list.
• Traverse the original linked list and using the values stored in the array adjust the next and random reference of cloned linked list nodes.

Python Implementation

class Node: 
    def __init__(self, data):

        self.data = data 
        self.next = None
        self.random = None


def cloneLinkedList(head):

    # Initialize a temp pointer
    temp = head

    # Making the array to store the data
    arr=[]

    # Making the copy of the linked list
    while temp is not None:
        new_node = Node(temp.data)
        # appending the values to arr
        arr.append([new_node, temp.next, temp.random])
        temp = temp.next


    temp = head
    i=0
    # Traversing the head and adjusting the pointers
    while temp is not None:
        new_node = arr[i][0]
        new_node.next = arr[i][1]
        new_node.random = arr[i][2]
        temp = temp.next
        i+=1

    # Return the of the clone list.
    return arr[0][0]

# making linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Making random pointers
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next

# Printing the linked list values
temp = head
print("Original Linked List is:")
while(temp):
    print("data:",temp.data, "random:",temp.random.data)
    temp = temp.next

# Printing the Cloned linked list values
temp = cloneLinkedList(head)
print("Cloned Linked List is:")
while(temp):
    print("data:",temp.data, "random:",temp.random.data)
    temp = temp.next

C++ Implementation

#include<bits/stdc++.h>
using namespace std;


// Linked list Definition
class Node{
    public:
    int data;
    // Next and random pointer
    Node *next, *random;

    Node(int data)
    {
        this->data = data;
        this->next = this->random = NULL;
    }
};

// linked list class
class LinkedList{
    public:
    Node *head;

    LinkedList(Node *head){
        this->head = head;
    }

    void push(int data){
        Node *node = new Node(data);
        node->next = head;
        head = node;
    }

    // Method to print the list.
    void print(){
        Node *temp = head;
        while (temp != NULL)
        {
            Node *random = temp->random;
            int randomData = (random != NULL)?
                         random->data: -1;
            cout << "data: " << temp->data << " ";
            cout << "random: " << randomData << endl;
            temp = temp->next;
        }
        cout << endl;
    }
LinkedList* cloneLinkedList(){
         // Initialize a temp pointer
        Node *temp = head;
        Node *newNode = NULL;

        // Make an array to store the data
        vector<vector<Node*>> arr;


        // Making the copy of the linked list
        while (temp != NULL){
            newNode = new Node(temp->data);
            vector<Node*> v1;
            v1.push_back(newNode);
            v1.push_back(temp->next);
            v1.push_back(temp->random);
            arr.push_back(v1);
            temp = temp->next;
        }

        temp = head;

        // Traversing the head and adjusting the pointer
        int i=0;
        while (temp != NULL){

            newNode = arr[i][0];
            newNode->next = arr[i][1];
            newNode->random = arr[i][2];
            temp = temp->next;
            i+=1;
        }

        // Return the head of cloned list
        return new LinkedList(arr[0][0]);
    }
};

// driver code
int main(){
    // Making a linked list
    LinkedList *mylist = new LinkedList(new Node(1));
    mylist->push(2);
    mylist->push(3);

    mylist->head->random = mylist->head->next->next;
    mylist->head->next->random = mylist->head;
    mylist->head->next->next->random = mylist->head->next;


    // Cloning the linked list
    LinkedList *clone = mylist->cloneLinkedList();

    cout << "Original linked list is:\n";
    mylist->print();
    cout << "\nCloned linked list is:\n";
    clone->print();
}

Java Implementation

import java.util.ArrayList;
import java.util.Map;

// Linked list Definition
class Node{
    int data;
    // Next and random pointer
    Node next, random;

    public Node(int data){
        this.data = data;
        this.next = this.random = null;
    }
}

// linked list class
class LinkedList{
    Node head;

    public LinkedList(Node head){
        this.head = head;
    }

    public void push(int data){
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;
    }


    void print(){
        Node temp = head;
        while (temp != null){
            Node random = temp.random;
            int randomData = (random != null)? random.data: -1;
            System.out.println("data: " + temp.data + " random: "+ randomData);
            temp = temp.next;
        }
    }

    public LinkedList cloneList(){
         // Initialize a temp pointer
        Node temp = this.head;
        Node newNode = null;


        // Map<Node, Node> hashMap = new HashMap<Node, Node>();
        ArrayList<ArrayList<Node>> arr = new ArrayList<ArrayList<Node>>();

        // Making the copy of the linked list
        while (temp != null){
            newNode = new Node(temp.data);
            ArrayList<Node> a1 = new ArrayList<Node>();
            a1.add(newNode);
            a1.add(temp.next);
            a1.add(temp.random);
            arr.add(a1);
            // hashMap.put(temp, newNode);
            temp = temp.next;
        }


        temp = this.head;

        // Traversing the head and adjusting the pointer
        int i=0;
        ArrayList<Node> t = new ArrayList<Node>();
        while (temp != null){
            t = arr.get(i);
            newNode = t.get(0);
            newNode.next = t.get(1);
            newNode.random = t.get(2);
            temp = temp.next;
            i+=1;
        }

        //return the head reference of the clone list.
        t = arr.get(0);
        return new LinkedList(t.get(0));
    }
}

// Driver Class
class Main{
    public static void main(String[] args){
        LinkedList list = new LinkedList(new Node(1));
        list.push(2);
        list.push(3);

        list.head.random = list.head.next.next;
        list.head.next.random = list.head;
        list.head.next.next.random = list.head.next;

        // Cloning the linked list
        LinkedList clone = list.cloneList();

        // Printint the linked list.
        System.out.println("Original linked list is:");
        list.print();
        System.out.println("\nCloned linked list is:");
        clone.print();
    }
}

Output:

Original Linked List is:
data: 1 random: 3
data: 2 random: 1
data: 3 random: 2

Cloned Linked List is:
data: 1 random: 3
data: 2 random: 1
data: 3 random: 2

Complexity Analysis

Time Complexity: O(N) => linked list has been traversed 2 times, so linear time is taken for this approach.
Space Complexity: O(N) => N space for storing N nodes in an array.

Approach 2 – Uses Constant Extra Space

To clone a linked list with next and random pointer, We’ll be implementing an algorithm that will require no extra space, lets see the algorithm for the same:

• In this approach, we will be using the approach of interweaving of nodes.
• In the original Linked List, make a copy of node 1 and place it between node 1 and 2, then make a copy of node 2 and place it between node 2 and 3. Continue by adding the duplicate of N after the Nth node.
• Now copy the random pointers in the interweaved nodes.
• After that, retrieve both the original and copied linked lists by rearranging the pointers

Python Implementation

class Node: 
    def __init__(self, data):

        self.data = data 
        self.next = None
        self.random = None


def cloneLinkedList(head):

    # Initializing a temp pointer    
    temp = head

    # Interweaving the copy of nodes 
    while(temp):
        node = Node(temp.data)
        node.next = temp.next
        temp.next = node
        temp = temp.next.next

    # Initializing a temp pointer again
    temp = head

    # Adjusting the random pointers of copied values
    while(temp):
        if(temp.random):
            temp.next.random = temp.random.next
        temp = temp.next.next

    # Initializing a temp pointer again
    temp = head

    # Initializing head of the clone value
    clone = temp.next

    # separating both the lists
    while(temp.next):
        a = temp.next
        temp.next = temp.next.next
        temp = a

    return clone

# making linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Making random pointers
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next

# Printing the linked list values
temp = head
print("Original Linked List is:")
while(temp):
    print("data:",temp.data, "random:",temp.random.data)
    temp = temp.next

# Printing the Cloned linked list values
temp = cloneLinkedList(head)
print()
print("Cloned Linked List is:")
while(temp):
    print("data:",temp.data, "random:",temp.random.data)
    temp = temp.next

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node *next,*random;
    Node(int x){
        data = x;
        next = random = NULL;
    }
};

void print(Node *start){
    Node *ptr = start;
    while (ptr){
        cout << "data: " << ptr->data << " random: "<< ptr->random->data << endl;
        ptr = ptr->next;
    }
}

Node* cloneLinkedList(Node *head){
     // Initialize a temp pointer
    Node* prev = head, *temp;

    // Interweaving the copy of nodes 
    while (prev){
        temp = prev->next;
        // Inserting node
        prev->next = new Node(prev->data);
        prev->next->next = temp;
        prev = temp;
    }

    //  Initializing a temp pointer again
    temp = head;

    // Adjusting the random pointers of copied values
    while (temp){
        if(temp->next)
            temp->next->random = temp->random ?
                                 temp->random->next : temp->random;

        temp = temp->next?temp->next->next:temp->next;
    }

    //  Initializing a temp pointer again
    temp = head;
    Node* clone = head->next;

    // Initializing head of the clone list
    Node* cloneHead = clone;

    // separating both the lists
    while (temp && clone){
        temp->next = temp->next? temp->next->next : temp->next;

        clone->next = clone->next?clone->next->next:clone->next;
        temp = temp->next;
        clone = clone->next;
    }

    return cloneHead;

}

// Driver code
int main(){
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    head->random = head->next->next;
    head->next->random = head;
    head->next->next->random = head->next;

    cout << "Original Linked List is: \n";
    print(head);

    cout << "\nCloned Linked List is: \n";
    Node *cloned_list = cloneLinkedList(head);
    print(cloned_list);

    return 0;
}

Java Implementation

class Code {

    static class Node {
        int data;
        Node next, random;
        Node(int x){
            data = x;
            next = random = null;
        }
    }

    static void print(Node start){
        Node ptr = start;
        while (ptr != null) {
            System.out.println("data: " + ptr.data + " random: "+ ptr.random.data);
            ptr = ptr.next;
        }
    }


    static Node cloneList(Node head){
         // Initialize a temp pointer
         Node prev = head, temp = null;

        // Interweaving the copy of nodes 
        while (prev != null) {
            temp = prev.next;

            // Inserting node
            prev.next = new Node(prev.data);
            prev.next.next = temp;
            prev = temp;
        }
        //  Initializing a temp pointer again
        temp = head;

        // Adjusting the random pointers of copied values
        while (temp != null) {
            if (temp.next != null)
                temp.next.random = (temp.random != null) ? temp.random.next : temp.random;

            temp = temp.next.next;                   
        }

        //  Initializing a temp pointer again
        temp = head;
        Node clone = head.next;

        // Initializing head of the clone list
        Node cloneHead = clone;

        // separating both the lists
        while (temp != null) {
            temp.next =temp.next.next;

            clone.next = (clone.next != null) ? clone.next.next : clone.next;
            temp = temp.next;
            clone = clone.next;
        }
        return cloneHead;
    }

    // Driver code
    public static void main(String[] args){
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        head.random = head.next.next;
        head.next.random = head;
        head.next.next.random = head.next;


        System.out.println("Original Linked List is: ");
        print(head);

        System.out.println("Cloned Linked List is: ");
        Node cloned_list = cloneList(head);
        print(cloned_list);
    }
}

Output:

Original Linked List is:
data: 1 random: 3
data: 2 random: 1
data: 3 random: 2

Cloned Linked List is:
data: 1 random: 3
data: 2 random: 1
data: 3 random: 2

Complexity Analysis

Time Complexity: O(N) => linked list has been traversed 3 times, so linear time is taken for this approach.
Space Complexity: O(1) => No Extra space is needed in this approach.

Approach 3 – Using Hashing

The idea for this approach is hashing, lets see the algorithm for the same:

• Go over the original linked list and create a data duplicate of it.
• Make a hash map of key value pair with original linked list node and copied linked list node to store both the nodes.
• Traverse the original linked list and using the values stored in hash map adjust the next and random reference of cloned linked list nodes.

Python Implementation

class Node: 
    def __init__(self, data):

        self.data = data 
        self.next = None
        self.random = None


def cloneLinkedList(head):

    # Initialize a temp pointer
    temp = head

    # Make a dictionary to store the data
    hashMap = {}

    # Making the copy of the linked list
    while temp is not None:
        new_node = Node(temp.data)
        hashMap[temp] = new_node
        temp = temp.next


    temp = head

    # Traversing the head and adjusting the pointers
    while temp is not None:
        new_node = hashMap.get(temp)
        new_node.next = hashMap.get(temp.next)
        new_node.random = hashMap.get(temp.random)
        temp = temp.next

    # Return the of the clone list.
    return hashMap[head]

# making linked list
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Making random pointers
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next

# Printing the linked list values
temp = head
print("Original Linked List is:")
while(temp):
    print("data:",temp.data, "random:",temp.random.data)
    temp = temp.next

# Printing the Cloned linked list values
temp = cloneLinkedList(head)
print()
print("Cloned Linked List is:")
while(temp):
    print("data:",temp.data, "random:",temp.random.data)
    temp = temp.next

C++ implementation

#include<bits/stdc++.h>
using namespace std;


// Linked list Definition
class Node{
    public:
    int data;
    // Next and random pointer
    Node *next, *random;

    Node(int data){
        this->data = data;
        this->next = this->random = NULL;
    }
};

// linked list class
class LinkedList{
    public:
    Node *head;

    LinkedList(Node *head){
        this->head = head;
    }

    void push(int data){
        Node *node = new Node(data);
        node->next = head;
        head = node;
    }

    // Method to print the list.
    void print(){
        Node *temp = head;
        while (temp != NULL){
            Node *random = temp->random;
            int randomData = (random != NULL)?
                         random->data: -1;
            cout << "data: " << temp->data << " ";
            cout << "random: " << randomData << endl;
            temp = temp->next;
        }
        cout << endl;
    }
LinkedList* cloneLinkedList(){
         // Initialize a temp pointer
        Node *temp = head;
        Node *newNode = NULL;

        // Make a map to store the data
        unordered_map<Node*, Node*> hashMap;

        // Making the copy of the linked list
        while (temp != NULL){
            newNode = new Node(temp->data);
            hashMap[temp] = newNode;
            temp = temp->next;
        }

        temp = head;

        // Traversing the head and adjusting the pointer
        while (temp != NULL){
            newNode = hashMap[temp];
            newNode->next = hashMap[temp->next];
            newNode->random = hashMap[temp->random];
            temp = temp->next;
        }

        // Return the head of cloned list
        return new LinkedList(hashMap[head]);
    }
};

// driver code
int main(){
    // Making a linked list
    LinkedList *mylist = new LinkedList(new Node(1));
    mylist->push(2);
    mylist->push(3);

    mylist->head->random = mylist->head->next->next;
    mylist->head->next->random = mylist->head;
    mylist->head->next->next->random = mylist->head->next;


    // Cloning the linked list
    LinkedList *clone = mylist->cloneLinkedList();

    cout << "Original linked list is:\n";
    mylist->print();
    cout << "\nCloned linked list is:\n";
    clone->print();
}

Java Implementation

import java.util.HashMap;
import java.util.Map;

// Linked list Definition
class Node{
    int data;
    // Next and random pointer
    Node next, random;

    public Node(int data){
        this.data = data;
        this.next = this.random = null;
    }
}

// linked list class
class LinkedList{
    Node head;

    public LinkedList(Node head){
        this.head = head;
    }

    public void push(int data){
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;
    }


    void print(){
        Node temp = head;
        while (temp != null){
            Node random = temp.random;
            int randomData = (random != null)? random.data: -1;
            System.out.println("data: " + temp.data + " random: "+ randomData);
            temp = temp.next;
        }
    }

    public LinkedList cloneList(){
         // Initialize a temp pointer
        Node temp = this.head;
        Node newNode = null;


        Map<Node, Node> hashMap = new HashMap<Node, Node>();


        // Making the copy of the linked list
        while (temp != null){
            newNode = new Node(temp.data);
            hashMap.put(temp, newNode);
            temp = temp.next;
        }


        temp = this.head;

        // Traversing the head and adjusting the pointer
        while (temp != null){
            newNode = hashMap.get(temp);
            newNode.next = hashMap.get(temp.next);
            newNode.random = hashMap.get(temp.random);
            temp = temp.next;
        }

        //return the head reference of the clone list.
        return new LinkedList(hashMap.get(this.head));
    }
}

// Driver Class
class Main{
    public static void main(String[] args){
        LinkedList list = new LinkedList(new Node(1));
        list.push(2);
        list.push(3);

        list.head.random = list.head.next.next;
        list.head.next.random = list.head;
        list.head.next.next.random = list.head.next;

        // Cloning the linked list
        LinkedList clone = list.cloneList();

        // Printint the linked list.
        System.out.println("Original linked list is:");
        list.print();
        System.out.println("\nCloned linked list is:");
        clone.print();
    }
}

Output:

Original Linked List is:
data: 1 random: 3
data: 2 random: 1
data: 3 random: 2

Cloned Linked List is:
data: 1 random: 3
data: 2 random: 1
data: 3 random: 2

Complexity Analysis

Time Complexity: O(N) => linked list has been traversed 2 times, so linear time is taken for this approach.
Space Complexity: O(N) => N space for storing N nodes in a HashMap.

Conclusion

• A linked list of length n is provided. Every node also has a random pointer that could refer to any node in the list or to null. The deep copy should be made up of exactly n new nodes, each of which has the value set to that of the corresponding node from the original copy (clone a linked list with next and random pointer).
• We can follow many approaches to clone a linked list with next and random pointer:
  • Approach 1: Uses O(n) extra space
    • Time Complexity: O(N) => linked list has been traversed 2 times, so linear time is taken for this approach.
    • Space Complexity: O(N) => N space for storing N nodes in an array.
  • Approach 2: Uses Constant Extra Space
    • Time Complexity: O(N) => linked list has been traversed 3 times, so linear time is taken for this approach.
    • Space Complexity: O(1) => No Extra space is needed in this approach.
  • Approach 3: Using Hashing
    • Time Complexity: O(N) => linked list has been traversed 2 times, so linear time is taken for this approach.
    • Space Complexity: O(N) => N space for storing N nodes in a hashmap.