请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

这题关键是random的指向，我们可以用哈希表来记录每个旧链表结点对应的新链表结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    Node *copyRandomList(Node *head) {
        if (head == NULL)
            return NULL;
        unordered_map<Node *, Node *> flag;
        Node *i = head;
        while (i != NULL) {
            flag[i] = new Node(i->val);
            i = i->next;
        }
        i = head;
        while (i != NULL) {
            if (i->random != NULL)
                flag[i]->random = flag[i->random];
            if (i->next != NULL)
                flag[i]->next = flag[i->next];
            i = i->next;
        }
        return flag[head];
    }
};

还有一种方法是先把新构造的结点放在原结点后面，这样不需要哈希表就能知道旧结点对应的新结点在哪

即old对应的new在old->next，最后还需要拆分两个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    Node *copyRandomList(Node *head) {
        if (head == NULL)
            return NULL;
        Node *i = head;
        while (i != NULL) {
            Node *mid = new Node(i->val);
            mid->next = i->next;
            i->next = mid;
            i = mid->next;
        }
        i = head;
        while (i != NULL) {
            if (i->random != NULL)
                i->next->random = i->random->next;
            i = i->next->next;
        }
        i = head;
        Node *ans = head->next;
        Node *j = ans;
        while (i->next != NULL) {
            i->next = j->next;
            i = j->next;
            if (j->next == NULL)
                break;
            j->next = i->next;
            j = j->next;
        }
        return ans;
    }
};