Cloning Linked List having Next and Random Pointer

Introduction

This question was asked by a colleague, although it seems to be simple at first but with given restrictions like running time and space limitations, it becomes tricky. You need to be good with Linked Lists to crack the right solution.

Here we try to define the problem in more detail.

Given a Linked List where each node contains two pointers next and random. The next pointer points to the immediate next node and the random pointer points to any random node in the linked list. Clone the linked list and return the head of the clone.

There are definitely certain conditions imposed on the solution:

  • The auxiliary space must be constant apart from the space required for clone.
  • The running time must be linear O(N), where N is the size of the linked list.

Approach – Cloning Linked List having Next and Random Pointer

Let us take an example linked list and work out the solution.
image1

In the above diagram, the blue color nodes are nodes of the input linked list. The black pointers are the next pointer and the red pointers are the random pointers.

Notice that C’s random pointer is pointing to null. The random pointers of A and E point to C. Also, you might have notice that the random pointers do not honor any direction. They can point backwards in to the list as well.

The O(N) solution goes as follows:

    • In pass one, for each node Ki, create a copy of Ki such that the copy is inserted between Ki and Ki+1 using the next pointers. In this process just change the next pointers and do not disturb the random pointers.
      image2
      In the above diagram, the red nodes are the cloned nodes.
    • After pass one is complete, start pass two and for each node Ki in the original list find out the node pointed by it’s random pointer, call it Ri. Assign the next of Ri to the random pointer of next node of Ki.

image3

The green pointers are the random pointers of the cloned nodes. For clarity I have drawn the green pointers in a different image. Ideally the two images must be merged to contain the red and green pointers. That means the resultant linked list after pass two would look like the linked list with the green pointers and the red pointers combined together.

  • Once pass two is complete, start pass three and separate the two lists. You know that all the nodes in the even position are a part of the cloned list.
    image4

 

Source – Cloning Linked List having Next and Random Pointer

You can get the complete code from the Github Link for TechieMe. Here is the important part of the code.

Analysis

Not much has to be said for the analysis. We are not using any extra space other than 3-4 pointers. The space used is for the clone list which is implicit. Also, the running time is linear i.e. O(N) where N is the number of nodes in the list. Of course we are running three passes and that increase the constant factor but it is very much linear.

Conclusion

The current code runs for three passes, of course we can merge the last two passes or all three passes in one, if written in a slightly compact manner.

Also, we can extend this problem to more links. The subtle idea behind linked list problems is conjugation. A set of moves which changes the original structure and a set of reverse moves which restores the original structure.

Don’t forget to subscribe to TechieMe to get updates on latest posts.

  • Aniket sagar

    Hey.
    How do you set the random pointers to point randomly somewhere in the list?
    Is there any in-built function that I am not aware of ?

    Thanks in advance!