Clone linked list with random pointer

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
clone linked list with random pointer

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 implementation

Clone linked list : Insert a new node

 while(current){
     Node_s * current_next = current->next;
     current->next  =  create_node(current->data);
     current->next->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.