第一种方式：

    1. /*
    2. // Definition for a Node.
    3. class Node {
    4. public:
    5.     int val;
    6.     Node* next;
    7.     Node* random;
    9.     Node(int _val) {
    10.         val = _val;
    11.         next = NULL;
    12.         random = NULL;
    13.     }
    14. };
    15. */
    17. class Solution {
    18. public:
    19.     Node* copyRandomList(Node* head) {
    20.         //在原有的链表的每一个节点后面都插入一个节点
    21.         Node* pt = head;
    22.         while(pt)
    23.         {
    24.             Node* pNew = new Node(pt->val);
    25.             pNew->next = pt->next;
    26.             pt->next = pNew;
    27.             pt= pt->next->next;
    28.         }
    29.         //把新插入的节点的random进行赋值
    30.         pt = head;
    31.         while(pt)
    32.         {
    33.             if(pt->random)
    34.             {
    35.                 pt->next->random = pt->random->next;
    36.             }
    37.             pt = pt->next->next;
    38.         }
    39.         //把新链表抠出来
    40.         pt = head;
    41.         Node* dummy = new Node(-1);
    42.         Node* newpt = dummy;
    43.         while(pt)
    44.         {
    45.             newpt->next = pt->next;
    46.             newpt = newpt->next;
    47.             pt->next = newpt->next;
    48.             pt = pt->next;
    50.         }
    51.         newpt->next = nullptr;
    52.         return dummy->next;
    54.     }
    55. };

    第二种，借助map，存的是新旧链表的node对

    /*
// 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) {
        map<Node*, Node*> mp;
        Node* pt = head;
        while(pt)
        {
            mp[pt] = new Node(pt->val);
            pt = pt->next;
        }

        pt = head;
        while(pt)
        {
            mp[pt]->next = mp[pt->next];
            if(pt->random)
            {
                mp[pt]->random = mp[pt->random];
            }
            pt = pt->next;
        }
        return mp[head];
    }
};

    第三种，借助map，存的是旧链表的节点的idx

    /*
// 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) {
        map<Node*, int> mp;
        vector<Node*> v;
        Node* pt = head;
        while(pt)
        {
            Node* newnode = new Node(pt->val);
            v.push_back(newnode);
            mp[pt] = v.size() - 1;
            pt = pt->next;
        }


        Node* dummy = new Node(-1);
        Node* newpt = dummy;
        pt = head;
        for(int i = 0; i < v.size(); i++)
        {
            newpt->next = v[i];
            newpt = newpt->next;
            if(pt->random)
                newpt->random = v[mp[pt->random]];
            pt = pt->next;
        }
        // newpt->next = nullptr;
        return dummy->next;


    }
};