## 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.

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 K
_{i}, create a copy of K_{i}such that the copy is inserted between K_{i}and K_{i+1}using the next pointers. In this process just change the`next`

pointers and do not disturb the`random`

pointers.

In the above diagram, the red nodes are the cloned nodes. - After pass one is complete, start pass two and for each node K
_{i}in the original list find out the node pointed by it’s random pointer, call it R_{i}. Assign the next of R_{i}to the random pointer of next node of K_{i}.

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.

## 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
private SpecialNode cloneList(SpecialNode inputList) { if (inputList == null) return null; // pass 1 SpecialNode node = inputList; SpecialNode clonedNode = new SpecialNode(node.data, node.next); node.next = clonedNode; node = node.next.next; while (node != null) { clonedNode = new SpecialNode(node.data, node.next); node.next = clonedNode; node = node.next.next; } // pass 2 node = inputList; while (node != null) { SpecialNode randomNode = node.random; if (randomNode != null) node.next.random = randomNode.next; node = node.next.next; } // pass 3 node = inputList; SpecialNode clonedHead = node.next; SpecialNode clonedTemp = node.next; while (node != null) { node.next = clonedTemp.next; node = node.next; if (node != null) { clonedTemp.next = node.next; clonedTemp = clonedTemp.next; } } return clonedHead; } |

## 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.