方法1 空间换时间

利用一个哈希表来记录原节点与复制节点之间的映射关系，根据映射关系修改复制节点的指针域

1. 遍历链表，创建复制节点，同时将原节点与复制节点的映射加入到哈希表中

2. 再次遍历链表，根据映射关系修改复制节点的指针域

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        // 原节点与复制节点之间的映射
        unordered_map<ListNode*, ListNode*> hash;
        auto p = head;
        while(p)
        {
            auto node = new ListNode(p->val);
            hash[p] = node;
            p = p->next;
        }

        // modify pointer
        p = head;
        while(p)
        {
            hash[p]->next = hash[p->next];
            hash[p]->random = hash[p->random];
            p = p->next;
        }
        return hash[head];
    }
};

方法2 不使用辅助额外空间

1. 遍历链表的同时，创建复制节点，并将节点添加到原节点的尾部

2. 再次遍历链表，修改复制节点的random指针域

3. 再次遍历链表，修改复制节点的next指针域，同时恢复原节点的next指针域

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        if(!head)   return nullptr;
        auto p = head;
        // copy
        while(p)
        {
            auto node = new ListNode(p->val);
            node->next = p->next;
            p->next = node;
            p = node->next;
        }

        auto newHead = head->next;

        // modify random
        p = head;
        while(p)
        {
            auto node = p->next;
            node->random = p->random ? p->random->next : nullptr;
            p = node->next;
        }

        // modify next
        p = head;
        while(p)
        {
            auto node = p->next;
            p->next = node->next;
            node->next = p->next ? p->next->next : nullptr;
            p = p->next;
        }
        return newHead;
    }
};