/*
knakul853
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {

        // just create a linked list with data .

        Node* newNode = new Node(0);

        Node* curNode = head;
        while(curNode)
        {
            Node* temp = curNode->next;

            curNode->next = new  Node(curNode->val);
            curNode->next->next = temp;
            curNode = temp;
        }

        // assign random pointer to the newly created linked list.

        curNode = head;
        while( curNode )
        {
            if( curNode->random != NULL )
            {
                curNode->next->random = curNode->random->next;
            }
            curNode = curNode->next ? curNode->next->next : curNode->next;
        }

        // extract the cloned and original linked list.

        Node* original = head;
        Node* copy = head ? head->next : head;

        Node* temp = copy;

        while( original && copy )
        {
            original->next=original->next ? original->next->next : original->next;
            copy->next = copy->next ? copy->next->next : copy->next;

            original = original->next;
            copy = copy->next;
        }

        return temp;



    }
};