转载自大佬的解法

C++ 代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    //需要记录旧节点和新节点对应关系
    unordered_map<ListNode*, ListNode*> hash;
    ListNode *copyRandomList(ListNode *head) {

        hash[nullptr] = nullptr;
        auto dup = new ListNode(-1), tail = dup;

        while(head)
        {
            if(!hash.count(head)) hash[head] = new ListNode(head->val);
            if(!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val);

            tail->next = hash[head];
            tail->next->random = hash[head->random];

            tail = tail->next;
            head = head->next;
        }

        return dup->next;

    }


};