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:

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.

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.