Clone a Linked List with random pointers
Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List, rather for each node in the original Linked List, a new node is created.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow. The only line of each test case contains the elements of the linked-list with random pointers. The line consists of nodes (value of node followed by its random pointer) separated by a single space. In case a node (next or random pointer) is null, we take -1 in its place. Each node is represented as a pair of a value and its random index where, Value: an integer representing the value of the node Random index: the index of the node where the random pointer points to, or -1 if it does not point to any node. For example, the input for the linked list depicted in the below image would be:

1 2 2 0 3 4 4 4 5 1 -1 Explanation: The head node of the linked-list is 1, and its random pointer points to a node present at index 2, i.e. node 3. The second node of the linked list is 2, and its random pointer points to a node present at index 0, i.e. node 1. In this way, input for each node is taken until a pair having its first part as -1 is encountered since it denotes a node having null value, i.e. end of the linked list.

Output Format:

For each test case, the only output line contains “True” if the linked list is successfully cloned. The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Clone a Linked List with random pointers

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List, rather for each node in the original Linked List, a new node is created.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains the elements of the linked-list with random pointers. The line consists of nodes (value of node followed by its random pointer) separated by a single space. In case a node (next or random pointer) is null, we take -1 in its place.

Each node is represented as a pair of a value and its random index where,
Value: an integer representing the value of the node
Random index: the index of the node where the random pointer points to, or -1 if it does not point to any node.

For example, the input for the linked list depicted in the below image would be:

1 2 2 0 3 4 4 4 5 1 -1

Explanation:

The head node of the linked-list is 1, and its random pointer points to a node present at index 2, i.e. node 3.
The second node of the linked list is 2, and its random pointer points to a node present at index 0, i.e. node 1.
In this way, input for each node is taken until a pair having its first part as -1 is encountered since it denotes a node having null value, i.e. end of the linked list.

Output Format:

For each test case, the only output line contains “True” if the linked list is successfully cloned.
The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
0 <= N <= 5 * 10^4
-10^5 <= data <= 10^5 and data != -1
-1 <= random index < N
where ‘T’ is the number of test cases, ‘N’ is the total number of nodes in the linked list, “data” is the value of the linked list node and “random index” is the index of the node where the random pointer points to.

Accepted Answer

1) First of all I made a clone of the Linked List using a head_reference and a current pointer
2) Then I simply reversed this cloned list using a next, previous and current pointer

Accepted Answer

Recursion

The basic idea is to consider the linked list like a binary tree. Every node of the Linked List has 2 pointers. So we consider these nodes as binary tree nodes. The head of the list becomes the root of the tree. So what we basically have to do now is to traverse the binary tree and clone it. The main issue that we need to tackle here is that of loops.

For example, we can have, 1 1 2 0 -1, we need to handle this in the code.

We start from the root node, and we keep traversing the tree (list), and we keep generating new nodes whenever we find a node for which the clone has not been generated. For example, we were at node A, and we used the next pointer to go to node B, and we created B’, which is a new node B with the same data. Also, say there was a random pointer from A to B. In this case, we don’t have to create yet another copy of node B because B’ already exists. We need to take care of this as well.

Steps are as follows:

Base case: If the current node is not present in the linked list, return null.
Check if we have already processed the current node (using HashMap), then simply return the cloned version of it.
Else, create a new node with the data same as the old node, i.e. copy the node.
Save this value in the HashMap. This is needed to avoid the loops which might be there while traversing the list.
Recursively copy the remaining linked list starting once from the next pointer and then from the random pointer.
Finally, update the next and random pointers for the new node created and return it.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the list.

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and height of a recursion tree could be ‘N’ in the worst case. Also, we are using a HashMap of size N to store the nodes of the list. Thus, the final space complexity is O(N + N) = O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the list.

In the worst case, we would be visiting 2 * N nodes i.e. N nodes using the next pointer and N nodes using the random pointer. Thus, the final time complexity is O(2 * N) = O(N).

C++ (g++ 5.4)

/*



	Time complexity: O(N)

	Space complexity: O(N)



	Where N is the number of nodes in the list



 */



#include 



Node *cloneLLHelper(Node *head, unordered_map &visited)

{

	// Base Condition

	if (head == NULL)

	{

		return NULL;

	}



	// If we have already processed the current node, simply return the cloned version of it.

	if (visited.find(head) != visited.end())

	{

		return visited[head];

	}



	// Create copy of the current node

	Node *node = new Node(head->data);



	/* Store this value in the map. This is needed since there might be

	   loops during traversal due to randomness of random pointers and this would

	   help us avoid them */

	visited[head] = node;



	/* Recursively copy the remaining linked list starting once from the next

	   pointer and then from the random pointer.

	   Thus we have two independent recursive calls.

	   Finally we update the next and random pointers for the new node created */

	node->next = cloneLLHelper(head->next, visited);

	node->random = cloneLLHelper(head->random, visited);



	return node;

}



Node *cloneLL(Node *head)

{



	// Map which holds old nodes as keys and new nodes as its values.

	unordered_map visited;



	return cloneLLHelper(head, visited);

}

Python (3.5)

'''



	Time complexity: O(N)

	Space complexity: O(N)



	Where N is the number of nodes in the list

'''



from collections import defaultdict





# List Node Class

class Node:

    def __init__(self, data):



        self.data = data

        self.next = None

        self.random = None



    def __del__(self):

        if(self.next):

            del self.next





def cloneLLHelper(head, visited):



    # Base Condition

    if (head == None):

        return None



    # If we have already processed the current node, simply return the cloned version of it.

    if (head in visited):

        return visited[head]



    # Create copy of the current node

    node = Node(head.data)



    '''

       Store this value in the map. This is needed since there might be

	   loops during traversal due to randomness of random pointers and this would

	   help us avoid them 

    '''

    visited[head] = node



    '''  

       Recursively copy the remaining linked list starting once from the next

	   pointer and then from the random pointer.

	   Thus we have two independent recursive calls.

	   Finally we update the next and random pointers for the new node created 

    '''

    node.next = cloneLLHelper(head.next, visited)

    node.random = cloneLLHelper(head.random, visited)



    return node





def cloneLL(head):



    # Map which holds old nodes as keys and new nodes as its values.

    visited = defaultdict(Node)



    return cloneLLHelper(head, visited)

Accepted Answer

HashMap

This iterative solution does not model the input as a tree and instead simply treats it as a LinkedList. The idea is to use Hashing to keep track of the links between the old nodes and the new nodes.

Algorithm:

We can solve this problem in two passes.

In the first pass over the original list, we can create an exact clone of the nodes of the original linked list. Additionally, we have a HashMap that maintains the old node to new node mapping. We will need it later on.

Note that the next and random pointers are not yet cloned.

In the second pass, we clone the next and the random pointer. The random pointer for A’ (A’ is the cloned version of the node A) is the HashMap value of the node pointed to by the random pointer of A.

Return the head of the cloned linked list.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the list.

We are using a HashMap containing a mapping from old list nodes to new list nodes. Since there are N nodes in the linked list, the space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the list.

We are traversing the linked list only twice. Thus, the time complexity is O(2 * N) = O(N).

C++ (g++ 5.4)

/*



	Time complexity: O(N)

	Space complexity: O(N)



	Where N is the number of nodes in the list



 */



#include 



Node *cloneLL(Node *head)

{

    // Initialize two references, one with original list's head

    Node *origCurr = head, *cloneCurr = NULL;



    // Map which contains node to node mapping of original and clone linked list

    unordered_mapstoreMapping;



    // Traverse the original list 

    while (origCurr != NULL)

    {

        cloneCurr = new Node(origCurr->data);

        storeMapping[origCurr] = cloneCurr;

        origCurr = origCurr->next;

    }



    // Adjusting the original list reference again

    origCurr = head;



    // Traverse original list again to adjust the next and random references of clone list using map

    while (origCurr != NULL)

    {

        cloneCurr = storeMapping[origCurr];

        cloneCurr->next = storeMapping[origCurr->next];

        cloneCurr->random = storeMapping[origCurr->random];

        origCurr = origCurr->next;

    }



    // Return the head reference of the cloned list

    return storeMapping[head];

}

Python (3.5)

'''



	Time complexity: O(N)

	Space complexity: O(N)



	Where N is the number of nodes in the list

'''



from collections import defaultdict





# List Node Class

class Node:

    def __init__(self, data):



        self.data = data

        self.next = None

        self.random = None



    def __del__(self):

        if(self.next):

            del self.next





def cloneLL(head):



    if(head == None):

        return None



    # Initialize two references, one with original list's head

    origCurr, cloneCurr = head, None



    # Map which contains node to node mapping of original and clone linked list

    storeMapping = defaultdict(Node)



    # Traverse the original list

    while (origCurr != None):



        cloneCurr = Node(origCurr.data)

        storeMapping[origCurr] = cloneCurr

        origCurr = origCurr.next



    # Adjusting the original list reference again

    origCurr = head



    # Traverse original list again to adjust the next and random references of clone list using map

    while (origCurr != None):



        cloneCurr = storeMapping[origCurr]



        if(origCurr.next != None):

            cloneCurr.next = storeMapping[origCurr.next]

        if(origCurr.random != None):

            cloneCurr.random = storeMapping[origCurr.random]

        origCurr = origCurr.next



    # Return the head reference of the cloned list

    return storeMapping[head]

Accepted Answer

Space Optimized

The idea is to associate the original node with its copy node in a single linked list. In this way, we don't need extra space to keep track of the new nodes.

Algorithm:

The algorithm is composed of the following three steps which are also 3 iteration rounds.

Iterate the original list and create a copy of each node. The copy
of each node follows its original immediately, i.e insert each copied node after its corresponding node in the original linked list.

For example, If the original linked list is: 1->2->3

The modified list will be, 1->1->2->2->3->3

Iterate the new list (original list after modification in step 1) and assign the random pointer for each duplicated/copied node.
Initialise a pointer to the node, ‘temp’ that points to the second node of the modified linked list.
Iterate the list again and restore the original list and extract the duplicate nodes, i.e separate the copied from the modified list.
The duplicated/copied nodes form a linked list which is the clone of the original linked list.
Return the head of this cloned linked list stored in ‘temp’.

Space Complexity: O(1)Explanation:

O(1)

Since the algorithm only uses constant space (not considering the size of the output list) , the final space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the list.

We are traversing the given linked list only thrice. Thus, the final complexity is O(3 * N) = O(N).

C++ (g++ 5.4)

/*

	

	Time complexity: O(N)

	Space complexity: O(1)



	Where N is the number of nodes in the linked list.



*/



Node *cloneLL(Node *head)

{

    Node *curr = head, *temp = NULL;



    // Insert duplicate nodes 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 = head;



    // Adjust the random pointers of the newly added nodes

    while (curr != NULL)

    {

        if (curr->next != NULL)

        {

            if (curr->random != NULL)

            {

                curr->next->random = curr->random->next;

            }

            else

            {

                curr->next->random = curr->random;

            }

        }



        // Move to the next newly added node by skipping an original node

        if (curr->next != NULL)

        {

            curr = curr->next->next;

        }

        else

        {

            curr = curr->next;

        }

    }



    Node *original = head, *copy = NULL;



    if (head != NULL)

    {

        copy = head->next;

    }



    // Save the start of copied linked list

    temp = copy;



    // Separate the original list and copied list

    while (original != NULL && copy != NULL)

    {

        if (original->next != NULL)

        {

            original->next = original->next->next;

        }



        if (copy->next != NULL)

        {

            copy->next = copy->next->next;

        }

        original = original->next;



        copy = copy->next;

    }



    // Return the head of the cloned list

    return temp;

}

Python (3.5)

'''

	

	Time complexity: O(N)

	Space complexity: O(1)



	Where N is the number of nodes in the linked list.

'''





# List Node Class

class Node:

    def __init__(self, data):



        self.data = data

        self.next = None

        self.random = None



    def __del__(self):

        if(self.next):

            del self.next





def cloneLL(head):



    curr, temp = head, None



    # Insert duplicate nodes after every node of original list

    while (curr != None):

        temp = curr.next



        # Inserting node

        curr.next = Node(curr.data)

        curr.next.next = temp

        curr = temp



    curr = head



    # Adjust the random pointers of the newly added nodes

    while (curr != None):

        if (curr.next != None):

            if (curr.random != None):

                curr.next.random = curr.random.next



            else:

                curr.next.random = curr.random



        # Move to the next newly added node by skipping an original node

        if (curr.next != None):

            curr = curr.next.next



        else:

            curr = curr.next



    original, copy = head, None



    if (head != None):

        copy = head.next



    # Save the start of copied linked list

    temp = copy



    # Separate the original list and copied list

    while (original != None and copy != None):

        if (original.next != None):

            original.next = original.next.next



        if (copy.next != None):

            copy.next = copy.next.next



        original = original.next



        copy = copy.next



    # Return the head of the cloned list

    return temp

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List, rather for each node in the original Linked List, a new node is created.

Input Format:

Output Format:

Note:

Constraints:

Top Bajaj Finserv Data Scientist interview questions & answers

Popular interview questions of Data Scientist

Top HR questions asked in Bajaj Finserv Data Scientist