/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(!head) return NULL; Node* current = head; // creating the copy of each and every node and joining it with the original node while(current){ Node* copy = new Node(current->val); copy->next = current->next; current->next = copy; current = copy->next; } // Assigning the random pointer current = head; while(current){ if(current->random){ current->next->random = current->random->next; } current = current->next->next; } // Making separate both list original linked list and the copy linked list current = head; Node* newHead = current->next; Node * newCurrent = newHead; while(current){ current->next = newCurrent->next; current = current->next; if(current){ newCurrent->next = current->next; newCurrent = newCurrent->next; } } return newHead; } };