## Clone linked list with random pointer

Given a linked list with every node has two pointers: next and random, ask is to clone this linked list with a random pointer to a new linked list.
The linked list will look like:

This problem can be solved using n extra spaces where we store a mapping of the existing node and new node in a hash map, then go through the linked list again, find the copy node of the current node, find copy node for its next, and link them. Then find the random pointer node of the current node, find the corresponding clone node of the random node, and link random pointer of the current nodes copy node to cloned random node. It takes 2 scans of the linked list as well.

However, the challenge is to do it in O(1) space complexity.

## Thought process

We are using hashmap to know the corresponding cloned node of a node in the linked list, can we do that without using hashmap? Can we use the linked list itself to store the information?
The idea here is to add the cloned node after the original node in the given linked list. For each node, we will insert the cloned node between the original node and its next node. After inserting the nodes as a subsequent node of the original node, we can easily get the mapping we were storing in the hashmap right?

Once, all the nodes are linked together, we can copy the random pointer of the original node to the random pointer of the cloned node as

```node.next.random = node.random.next
```

The last step will be to separate the two lists. We go through the list, for each node, we will get the cloned node by node.next, next of the current original node should be the next of the cloned node.

```Node clonedNode = node.next;
node.next = cloneNode.next;
```

Last, we have to link the cloned nodes next to node.next.next and move forward to the next node of the original node.

Overall, this implementation required 3 passes to the linked list, first to insert nodes in between, then to copy the random pointers and then to detach the cloned linked list. Pass 2 and 3 can be combined but it is easier to understand that way.

### Show me the implementation

```/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;

public Node() {}

public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {

Node current = head;
if(head == null) return null;

/* Step 1. create clones of each node and
insert them next to the original node.
List [1,2,3] will look like [1,1,2,2,3,3]
*/
while(current != null){
//create node.
Node newNode = new Node(current.val);

//Insert to the next of current
newNode.next = current.next;
current.next = newNode;

current = newNode.next;
}

/* Step 2. Copy the random pointers.
The cloned node's random will point to the
next of the original node.
*/
current = head;
while(current != null){
if(current.random != null){
//current.next is cloned node. it's random points
//to next of current node's random.
current.next.random = current.random.next;
}
current = current.next.next;
}

current = head;
Node newHead = head.next;
/* Step 3 : Detach the cloned list from the original list */
while(current != null){
Node node = current.next;
current.next = current.next.next;
//IMPORTANT: Check for the last node.
if(current.next != null){
node.next = current.next.next;
}
current = current.next;
}

//Return new head
return newHead;
}
}
```

The time complexity of above implementation is O(N) and space complexity is O(1)