Copy List with Random Pointer Problem (with Solution)

Linked List is always a complex subject to crack for beginners. The problems asked in technical interviews are even more difficult, but not impossible. In this article, we will solve the Copy list with random pointers problem, with implementation in C++, Java, and Python.

Copy List with Random Pointer problem

Before moving forward, remember that there are two different methods to copy a node in a linked list.

One is a shallow copy in this you create a node whose address is the same as the original node. So if you made any changes in this it will also reflect in the original node. Another way is a deep copy in this you create a node and copy the values of the original node.

In the Copy List with Random Pointer problem, we are given a linked list with an additional random pointer that can point to any node. We need to create a deep copy of this linked list in which none of the nodes have the same address as the original list.

Let’s look at the example for more clarity:

Example for Copy List with Random Pointer problem

In this, we are given a linked list of 3 nodes x, y, and z as shown. We have to create 3 more nodes which are exact replicas of x,y, and z the only difference is that they have different addresses.

Hash-Map Approach

The brute force approach is to first create n (n is the number of nodes in a linked list.) different nodes having the same values as the original linked list. Store each node address in a linked list as a key in the hash map and the value of those keys is the address of newly created nodes by you.

After mapping iterate a loop and assign next and random values to the newly created nodes.

Let’s examine this approach through an example:

First, make new nodes for each node and store the address of the previous node as a key in the map and the newly created node address as a value of that key.
Iterate over the map and point the next pointer of the current value to the value of the key which is the next pointer to the current key.
Iterate over the map and point the random pointer of the current value to the value of the key which is the random pointer to the current key.

Return the value of the first node of the liked list.

The time complexity for the above code is O(n log(n) ). We are storing each node into the map which took O(n log(n) ) time. We are also iterating over the map whose time complexity is O(n), so the overall time complexity is O(n log(n) ).

The space complexity for the above code is O(n) as we are storing each node on the map. (n is the number of nodes in a linked list.)

Optimized Approach

In the above approach, we are using an extra space which can be reduced if we do not use the hash map. Also storing values on the map takes extra time. In this approach, we will create a new node next to each node as a copy of the original nodes.

Let’s understand this approach step by step:

First, iterate over the linked list.
Make a new node at each iteration. Now point the new node to the next of the current node and the current node next as the new node.
Now move to the next of new nodes.
Repeat the same process till you reach the last node.
Now again iterate the linked this and check the random pointer to the current pointer. Make Original->next->random = Original->random->next.
Move to the next to the next of the original pointer and repeat the same process. Until you reach the null value.

Example of optimized approach to copy linked list with random pointer

Let’s examine the code for the given linked list.

C++ Code

Below is the implementation of the optimized code in C++:

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

class node {
    public:
    int val;
    node *next, *random;
    node(int x) {
        val = x;
        next = random = NULL;
    }
};

node* new_list(node* head) {
   
	if (head == NULL) {
		return NULL;
	}
	
	node* curr = head;
	while (curr != NULL) {
		node* temp = new node(curr->val);
		temp->next = curr->next;
		curr->next = temp;
		curr = temp->next;
	}
	
	curr = head;
	while (curr != NULL) {
		if (curr->random != NULL) {
			curr->next->random = curr->random->next;
		}
		curr = curr->next->next;
	}
	
	curr = head;
	node* clonedhead = head->next;
	node* clonedcurr = head->next;
	while (clonedcurr->next != NULL) {
		curr->next = curr->next->next;
		clonedcurr->next = clonedcurr->next->next;
		curr = curr->next;
		clonedcurr = clonedcurr->next;
	}
	curr->next = NULL;
	clonedcurr->next = NULL;
	
	return clonedhead;
}

void printList(node* head)
{
	cout << head->val << "(";
	if(head->random) cout<<head->random->val;
	else cout<<"NULL";
		cout << ")";
	head = head->next;
	while (head != NULL) {
		cout << " -> " << head->val << "(";
		if(head->random) cout<< head->random->val; 
		else cout<<"NULL";
		cout<< ")";
		head = head->next;
	}
	cout << endl;
}

int main()
{
	// Creating a linked list with a random pointer
	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;

	// the original list
	cout << "Original linked list: ";
	printList(head);
    
	node* sol = new_list(head);
	
	cout << "Cloned linked list: ";
	printList(sol);
	
	return 0;
}

Java Code

Here is the solution in Java:

import java.util.HashMap;

class Node {
    public int val;
    public Node next, random;

    public Node(int x) {
        val = x;
        next = random = null;
    }
}

public class CopyListWithRandomPointer {

    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Node curr = head;

        // Create a new node for each existing node and insert it after the original node
        while (curr != null) {
            Node temp = new Node(curr.val);
            temp.next = curr.next;
            curr.next = temp;
            curr = temp.next;
        }

        curr = head;

        // Assign random pointers for the new nodes
        while (curr != null) {
            if (curr.random != null)
                curr.next.random = curr.random.next;
            curr = curr.next.next;
        }

        // Separate the original and cloned nodes
        curr = head;
        Node clonedHead = head.next;
        Node clonedCurr = head.next;

        while (clonedCurr.next != null) {
            curr.next = curr.next.next;
            clonedCurr.next = clonedCurr.next.next;
            curr = curr.next;
            clonedCurr = clonedCurr.next;
        }

        curr.next = null;
        clonedCurr.next = null;

        return clonedHead;
    }

    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "NULL") + ")" + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        CopyListWithRandomPointer solution = new CopyListWithRandomPointer();

        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;

        System.out.print("Original linked list: ");
        printList(head);

        Node sol = solution.copyRandomList(head);

        System.out.print("Cloned linked list: ");
        printList(sol);
    }
}

Python Code

We can also implement it in Python to copy the list with a random pointer:

class Node:
    def __init__(self, x):
        self.val = x
        self.next = None
        self.random = None

def copyRandomList(head: 'Node') -> 'Node':
    if head is None:
        return None

    curr = head

    # Create a new node for each existing node and insert it after the original node
    while curr:
        temp = Node(curr.val)
        temp.next = curr.next
        curr.next = temp
        curr = temp.next

    curr = head

    # Assign random pointers for the new nodes
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Separate the original and cloned nodes
    curr = head
    cloned_head = head.next
    cloned_curr = head.next

    while cloned_curr.next:
        curr.next = curr.next.next
        cloned_curr.next = cloned_curr.next.next
        curr = curr.next
        cloned_curr = cloned_curr.next

    curr.next = None
    cloned_curr.next = None

    return cloned_head

def print_list(head: 'Node'):
    current = head
    while current:
        print(f"{current.val}({current.random.val if current.random else 'NULL'}) ->", end=" ")
        current = current.next
    print("NULL")

if __name__ == "__main__":
    # Creating a linked list with random pointer
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)

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

    # the original list
    print("Original linked list: ", end="")
    print_list(head)

    sol = copyRandomList(head)

    print("Cloned linked list: ", end="")
    print_list(sol)

Output:

 Original linked list: 1(3) -> 2(1) -> 3(NULL)
 Cloned linked list: 1(3) -> 2(1) -> 3(NULL)

The time complexity is now reduced to O(n) as we are just iterating over the linked list two times. The Space Complexity is reduced to O(1) as we are not using any extra space.

We can compare the difference the optimized approach makes to copy the list with a random pointer:

Approach	Time Complexity	Space Complexity	Description
Brute Force	O(n log(n))	O(n)	We are storing the values into the map which requires log(n) time complexity.
Optimized Approach	O(n)	O(1)	We are just iterating the linked list two times which reduces the time complexity from O(n log(n)) to O(n).

Conclusion

This article helps us understand various approaches to solving the leetcode problem for copying a list with a random pointer. There are more leetcode solutions to master Data Structures and Algorithms.