直观做法，用哈希表复刻链表。时间：$O(n)$， 额外空间：$O(n)$

/**
 * 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) {
        if (!head) return head;
        unordered_map<ListNode*, ListNode*> pos;    //哈希表储存映射

        pos[NULL] = NULL;
        for (auto p = head; p; p = p->next)
            pos[p] = new ListNode(p->val);

        for (auto p = head; p; p = p->next)
        {
            pos[p]->next = pos[p->next];            //映射后的next=先next再映射
            pos[p]->random = pos[p->random];
        }

        return pos[head];
    }
};

时间：$O(n)$， 额外空间：$O(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) {
        for (auto p = head; p;)                     //在每个点后面添加一个它的赋值复制
        {
            auto np = new ListNode(p->val);
            auto next = p->next;
            p->next = np;
            np->next = next;
            p = next;
        }

        for (auto p = head; p; p = p->next->next)   //复制random指针
            if (p->random)
                p->next->random = p->random->next;

        //分离两个链表
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        for (auto p = head; p; p = p->next)
        {
            cur->next = p->next;
            cur = cur->next;
            p->next = p->next->next;
        }

        return dummy->next;
    }
};