Clone a linked list with next and random pointer

3 min readSep 3, 2020

We have a double linked list where each node consists of three pointers data, random and next. Now our task is to clone this linked list

Let’s first dive deep into the 1st solution of this problem

This method stores the next and random pointer (of original list) in an array first, then modifies the original Linked List (to create copy), creates a copy. And finally restores the original list.

First we will make a simple copy of the above linked list in which next is pointing to the next node and random is currently pointing to null.

2. The next pointer of the original linked list will point to the node of the copied linked list

3. For all random pointers in the copied linked list give address of respective nodes in the original linked list.

4. Next we will perform the following statement

copied->random=copied->random->random->next

This will link the random pointers.

Now we will see how it works

copied->random

So let’s first see the left hand side of this

So for 1st node

copied->random=null

let’s now look for the 2nd node

From the above diagram it’s clear that the random pointer of 2nd node of copied linked list points to the first node which was actually same as in original linked list

So copied->random->random->next consists of 1st node

So RHS for 2nd node copied->random=address of the 1st node

To make you more clear about this approach let’s do it for the 3rd node also.

So from the above diagram it is clear that random pointer 3rd Node of the copied list stores the 5th node of the copied list which is the same case as that of the original one.