# Clone a linked list with next and random pointer

Yukti Kumari
Last Updated: May 13, 2022

## Introduction

In this article, we will discuss a very interesting problem - Clone a linked list with next and random pointer. There are problems where you need to clone a singly linked list or a doubly-linked list, but this one is a bit different and tricky from these traditional questions. We will discuss various approaches to solve this problem and see how we can improve time and space complexities to move towards a more optimised version.

In this, the linked list consists of nodes, and each node has two pointers. One of the pointers points to the next node, and it is called the Next pointer.  The other pointer can point to any node present in the list or can be null, and hence we refer to it as a random pointer.

Let’s see the problem statement -

Given a linked list in which every node has two pointers. One of the pointers points to the next node, and it is called the Next pointer. The other pointer can point to any node present in the list or can be null, and hence we refer to it as a random pointer.

Note that we have to create a deep copy of the linked list.

Example -

## Approach 1

Forget about the random pointers and think that if the question had been to clone a normal singly linked list, what would our approach have been?

We would then simply traverse the given list, and for each node in the original list, create a new node in the clone and set up the pointers correctly.

Here, also, we will do the same in the first step. i.e., clone the linked list with the next pointers without caring about the random pointers.

Next, we create a hashmap. The key of the hashmap is an original node, and its corresponding value is the new node that we create while iterating the original list.

In the second iteration over the original list,  we clone the random pointer using this relation -

cloned_node -> random =  map[original_node -> random]

where map[original_node -> random] is the node in the cloned list corresponding to the node original_node->random in the original list.

C++ Implementation:

Output:

Time Complexity:

The time complexity of this method is O(n), where n is the number of nodes in the given linked list. Since we traverse the original linked list 2 times to construct the cloned list. Total complexity is  O(n)+O(n) = O(2*n), which is ultimately O(n).

Space Complexity:

We are using a hashmap to map the old list nodes to the new list nodes. Since extra space used is equal to the number of nodes in the list, the space complexity becomes O(n), where n is the number of nodes in the linked list.

## Approach 2 (clone a linked list with next and random pointer in O(1) space)

In the previous approach, we used a hash map which resulted in a space complexity of O(n).

In this approach, we will proceed in the following steps to reduce the space complexity -

• Create a copy of Node1 and insert it between Node1 and Node2 in the original linked list itself. Similarly, create a copy of Node 2 and insert it between Node 2 and Node 3 in the original linked list. Repeat this process for all the nodes.

In general, insert a copy of the Node-i between Node_i and Node_i+1. For the last node, insert its copy after it.

Now, for all the nodes of the original list -

original->next = cloned_node

• In this step, we will set the random pointers of each cloned node in this way -

(original->next)->random = (original->random)->next

because original->next is nothing but a copy of the original node and (original->random)->next is nothing but a copy of random.

In this figure, the random pointers of all the copy nodes have been initialized.

• Now, restore the original linked list and clone of the linked list in a single traversal in the following way -

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

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

The first list is the original list and the second one is the clone of the linked list which we just constructed.

C++ Implementation:

Output:

Time Complexity: It is O(n) because in total we make three passes over the entire linked list. The first time, to insert a copy of the original nodes after each of them. The second time, to set up the random pointer of the copy nodes correctly. The third time, to separate the original linked list and clone of the linked list. So, total operations are O(3*n) ⋍ O(n), which is linear complexity.

Space Complexity:

It is O(1). Since we don’t use any extra data structure in our algorithm apart from just some variables, it needs only constant space.

1. What is a deep copy in a linked list?

A deep copy of a linked list means that for every node in the original linked list, we create a new node in the new list and then copy the values of the original node to it. It differs from the shallow copy in which we only copy the references of the nodes of the original linked list.

2. How do you multiply two linked lists?

3. How do doubly-linked lists work?

In a doubly-linked list, every node has a data field and two link fields, namely the next pointer and a previous pointer. The next pointer points to the next node in the list, and the previous pointer points to the previous node.

4. What is a multi-linked list?

A multi-linked list is a linked list where each node may have pointers to more than one node of the linked list. A doubly-linked list is an example of a multi-linked list that has two pointers.

## Key Takeaways

In this article, we learned to solve an interesting version to clone a linked list with next and random pointers. We saw two approaches to solve it. One of the ways was using hashmap to store the old node to new node mapping. But this turned out to be space inefficient. Then, we built up the solution to gain constant space complexity and hence moved to an optimized solution.

You should not stop here. There are many interesting problems related to linked list like Merging two sorted linked lists,  Print Linked List in reverse order,  Count inversion,  Add 1 to a linked list,  Check linked list palindrome

Practising makes the concepts more clear and makes you confident about your problem-solving skills.

Do check out CodeStudio to practice commonly asked interview questions to ace your next technical interview.