Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

/*

// Definition for a Node.

class Node {

public:

    int val;

    Node* next;

    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {

        val = _val;

        next = _next;

        random = _random;

    }

};

*/

class Solution {

public:

    Node* copyRandomList(Node* head) {

        map<Node*, Node *> mp;

        

        Node *new_node = NULL;

        new_node = copy(head, mp);

        

        process(new_node, head, mp);

        return new_node;

    }

    

    Node* copy(Node* head,map<Node*, Node*>& mp) {

        if (head == NULL) {

            return NULL;

        }

        Node *new_node = new Node(head -> val, NULL, head);

        mp[head] = new_node;

        new_node -> next = copy(head -> next, mp);

        return new_node;

    }

    

    void process(Node *new_node, Node *head, map<Node *, Node *>& mp) {

        Node *trav = new_node;

        while (trav != NULL) {

            trav -> random = (trav -> random -> random == NULL ? NULL : mp[trav -> random -> random]);

            trav = trav -> next;

        }

    }

};

================== Alternative one (without using map) ==========

1 -> 1' -> 2 -> 2' -> 3 -> 3'

node -> next -> random = (node -> random != NULL ? node -> random -> next : NULL);
node = node -> next -> next


===============

/*

// 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 == NULL) {

            return NULL;

        }

        

        // Create a clone of every node

        Node *new_head = NULL;

        Node *temp = head;

        while (temp != NULL) {

            Node *temp_next = temp -> next;

            Node *new_node = new Node(temp -> val);

            new_node -> next = temp_next;

            temp -> next = new_node;

            temp = temp_next;

        }

        

        // Handle random assignment

        temp = head;

        while (temp != NULL && temp -> next != NULL) {

            temp -> next -> random =

                (temp -> random != NULL ? temp -> random -> next : NULL);

            temp = temp -> next -> next;

        }

        

        // Handle next assignment.

        temp = head;

        new_head = head -> next;

        while (temp != NULL && temp -> next != NULL) {

            Node *new_head_next = temp -> next;

            temp -> next = temp -> next -> next;

            new_head_next -> next =

                (temp -> next != NULL ? temp -> next -> next : NULL);

            temp = temp -> next;

        }

        return new_head;

    }

};