Home » Interview Questions » LinkedList Interview Questions » Clone a Linked List with next and random pointer

Clone a Linked List with next and random pointer


Given a doubly linked list, in which one pointer is pointing to the next node just like in a singly linked list.

The second pointer however can point to any node in the list.


Method 1

Time Complexity : O(n)
Space Complexity : O(n)

In this method the main idea is to store the next and rand mappings of original list in an array first, then modify the original list to create a copy and then restore the original list.


1. Create all nodes in copy linked list using “next” pointers

2. Store the node and its “next” pointer mappings of original linked list in an array ie, to restore the original linked list

3. Change “next” pointer in original linked to point to the corresponding node in the copy linked list

4. Now, for all nodes in copy list point the “rand” pointer to the corresponding node

5. Finally, we will change the “rand” pointer for all nodes in  copy linked list as shown below
copy_list->rand = copy__list->rand->rand->next

6. Restore the next pointers in original list from stored mappings

The above algoorithm can be clearly explained in below diagram

Method 2

Time Complexity : O(n)
Space Complexity : O(1)


1. Create a copy of every node in the list and insert it in original list between current and next node

2. Now, copy the rand link in this fashion
original->next->rand = original->rand->next
This works because original->next is nothing but copy of original and original->rand is nothing but copy of rand.

READ  Merge Two Sorted Lists Leetcode

3. Now restore the original and creating a copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;
Make sure that last element of original->next is NULL.


How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions