解法1：哈希表

/**
 * 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:
    ListNode *copyRandomList(ListNode *head) {
        // 哈希表, 空间复杂度O(n)
        unordered_map<ListNode* , ListNode *> REC;
        REC[nullptr] = nullptr;

        ListNode *p = head;
        while(p != nullptr){
            REC[p] = new ListNode(p->val);
            p=p->next;
        }

        p=head;
        while(p!=nullptr){
            if(p->next) REC[p]->next = REC[p->next];
            if(p->random) REC[p]->random = REC[p->random];
            p=p->next;
        }

        return REC[head];
    }
};

解法2：复制法

/**
 * 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:
    ListNode *copyRandomList(ListNode *head) {
        // 复制法: 空间复杂度O(1)
        ListNode *p = head;
        // 复制节点
        while(p!=nullptr){
            ListNode *node = new ListNode(p->val);
            node->next=p->next;
            p->next=node;
            p=p->next->next;
        }

        // 设置指针
        p=head;
        while(p!=nullptr){
            if(p->random)
                p->next->random=p->random->next;
            p=p->next->next;
        }

        // 分离链表
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        p=head;
        while(p!=nullptr){
            cur->next=p->next;
            cur=cur->next;
            p->next=p->next->next; // 恢复链表原始状态
            p=p->next;
        }
        return dummy->next;
    }
};