对链表操作比较深入地考察。由浅入深使用三种方法来做。

方法一：暴力求解

双重for循环的主要目的是查找random节点的位置。时间复杂度是 $O(n^2)$
分为两步实现：
1. 根据next指针新建链表
2. 双重for循环，每次查找到一个random节点，就重新遍历查找其位置

/**
 * 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) {
        ListNode* newList = new ListNode(-1);
        auto nextNode = newList;

        //第一步，根据next指针新建链表
        for (auto node = head; node; node = node->next) {
            ListNode* newNode = new ListNode(node->val);
            nextNode->next = newNode;
            nextNode = nextNode->next;
        }

        // 第二步，双重for循环，每次查找到一个random节点，就重新遍历查找其位置
        for (auto curNode = newList->next, node = head; curNode && node; ) {
            if (node->random) {
                auto r_curNode = newList->next, r_node = head;
                while (r_node != node->random && r_node) {
                    r_curNode = r_curNode->next;
                    r_node = r_node->next;
                }
                curNode->random = r_curNode;
            }
            curNode = curNode->next;
            node = node->next;
        }

        return newList->next;
    }
};

方法二：使用hash表求解

因为hash表查找的时间复杂度是O(1)，因此通过该方法可以把之前暴力求解中的 $O(n^2)$ 的复杂度用空间来代替。
分两步来实现：
1. 建立原链表和目标链表的对应关系，存储到hash表中
2. 遍历原链表，查看random节点，根据hash表中存储的对应关系，建立目标链表的random节点关系

/**
 * 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) {
        unordered_map<ListNode*, ListNode*> hash;
        ListNode* newList = new ListNode(-1);
        auto nextNode = newList;

        // 第一步，建立原链表和目标链表的对应关系，存储到hash表中
        for (auto node = head; node; node = node->next) {
            ListNode* newNode = new ListNode(node->val);
            nextNode->next = newNode;
            hash.insert({node, newNode});
            nextNode = nextNode->next;
        }

        // 第二步，遍历原链表，查看random节点，根据hash表中存储的对应关系，
        // 建立目标链表的random节点关系
        for (auto node = head; node; node = node->next) {
            if (node->random) {
                auto curNode = hash[node];
                curNode->random = hash[node->random];
            }
        }

        return newList->next;
    }
};

方法三：并行求解

主要思路是通过复制链表的方式，来解决random节点的查找问题。大体可以分为三步：
1. 链表所有节点中间都插入一个复制节点，作为并行链表
2. 遍历新链表，遇到Random节点后对应改变并行链表中的节点
3. 提取出并行链表

/**
 * 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 node = head; node; ) {
            auto nextNode = node->next;
            ListNode* newNode = new ListNode(node->val);
            newNode->next = node->next;
            node->next = newNode;
            node = nextNode;
        }

        // 第二步：遍历新链表，遇到Random节点后对应改变并行链表中的节点
        for (auto node = head; node; node = node->next->next) {
            if (node->random) {
                node->next->random = node->random->next;
            }
        }

        // 第三步：提取出并行链表
        ListNode* newList = new ListNode(-1);
        auto nextNode = newList;

        for (auto node = head; node; node = node->next) {
            nextNode->next = node->next;
            nextNode = nextNode->next;
            node->next = node->next->next;
        }

        return newList->next;
    }
};