**Clone linked list**

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-&gt;next; current-&gt;next = create_node(current-&gt;data); current-&gt;next-&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; void freeList(Node * head){ if(!head) return; Node * current = head; Node * next = head; while(current){ next = current->next; free(current); current = next; } } void push(Node **head, int value){ if(*head == NULL){ (*head) = (Node *)malloc(sizeof(Node)); (*head)->value = value; (*head)->next = NULL; } else{ Node * newNode = (Node *)malloc(sizeof(Node)); if(newNode){ newNode->value = value; newNode->next = (*head); *head = newNode; } } } 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; } Node * cloneLinkedList(Node * node){ 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 Node * cloneHead = current->next; while(current){ Node * clone = current->next; if(current->random){ clone->random = current->random->next; } current = clone->next; } current = node; //Segregate two linked list 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 return cloneHead; } 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); addRandomPointer(L1,1,6); addRandomPointer(L1,2,5); addRandomPointer(L1,3,1); addRandomPointer(L1,4,2); addRandomPointer(L1,5,4); addRandomPointer(L1,6,3); printList(L1); Node *cloneHead = cloneLinkedList(L1); freeList(L1); printList(cloneHead); return 0; }

Time complexity of algorithm to **clone a linked list with random pointer** is O(N) and space complexity is O(1).

To see more interview problems on linked lists, please follow : Linked lists problems

Please share if there is something is wrong or missing. If you are interested in contributing to website or an interview experience to share, please contact us.