# Clone linked list with random pointer

Given a linked list with next and arbitrary random pointer, clone linked list with exactly same structure. Linked list with random pointer looks something like

Cloning a linked list with random pointer problem can be easily solved using extra space, O(n), where next and arbitrary pointer mapping of each node of given linked list is stored. However, challenge is to solve this problem in O(1) space complexity.

Idea is to add a node between every two nodes of original linked list which eventually becomes node in clone linked list. For example, in above list, a new node will be added between 1 and 2 with value 1, between 2 and 3 with value as 2 and so on.

While adding new node, make sure that next pointer of original node points to the new node and next pointer of new node points to second node in original linked list.

After addition of new nodes, original list looks like

### Clone linked list : Insert a new node

``` while(current){
Node_s * current_next = current-&amp;gt;next;
current-&amp;gt;next  =  create_node(current-&amp;gt;data);
current-&amp;gt;next-&amp;gt;next = current_next;
current = current_next;
}
```

Now we can access clone node with next pointer of node. With given structure of original list, random pointer of new node can be accessed as original_node->next->random. To set random pointer of new node as per original node, do this:

```newNode = currentNode->next //This step gives new node to be created.

currentNodeRandom = currentNode->random;
if(currentNodeRandom)
newNode->random = currentNodeRandom->next;```
```while(current){
Node * clone = current->next;
if(current->random){
clone->random = current->random->next;
}
current = clone->next;
}
```

In last, we need to segregate two linked list and new linked list will be clone of original linked list.

```while(current){
Node * clone  = current->next;
current->next = clone->next;
if(clone->next){
clone->next = clone->next->next;
}
current = current->next;
}
```

Complete implementation

```#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int value;
struct node *next;
struct node *random;
} Node;

while(current){
next = current->next;
free(current);
current = next;
}
}

}
else{
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->value = value;
}
}
}
void addRandomPointer(Node *L1, int a, int b){

Node * first  = L1;
Node * second = L1;

while(first){
if(first->value == a)
break;
first = first->next;
}
while(second){
if(second->value == b)
break;
second = second->next;
}

if(first)
first->random = second;
}

Node * createNode(int val){

Node * newNode =  (Node *)malloc(sizeof(Node));
if(newNode){
newNode->value = val;
newNode->next = NULL;
}
return newNode;
}

if(!node) return NULL;
Node * current = node;

//First insert clone nodes in original linked list.
while(current){
Node * currentNext = current->next;
current->next  =  createNode(current->value);
current->next->next = currentNext;
current = currentNext;
}
current = node;

//Now copy arbit pointer of each node to cloned list
while(current){
Node * clone = current->next;
if(current->random){
clone->random    = current->random->next;
}
current = clone->next;
}

current = node;

while(current){
Node * clone  = current->next;
current->next = clone->next;
if(clone->next){
clone->next = clone->next->next;
}
current = current->next;
}
//return head pointer to the calling function
}

void printList( Node *current){
while(current){
printf("%d ", current->value);
current = current->next;
}
printf("\n");
}

int main(){
Node * L1 = NULL;
push(&L1,1);
push(&L1,2);
push(&L1,3);
push(&L1,4);
push(&L1,5);
push(&L1,6);

printList(L1);