32 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

提示：

• 0 <= n <= 1000
• $-10^4$ <= Node.val <= $10^4$
  Node.random 为 null 或指向链表中的节点。
  注意：本题与主站 138 题相同：138

题解1 哈希表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:

    Node* copyRandomList(Node* head) {
        if(! head) return nullptr;
        Node *p, *q, *f, *cphead;
        f = p = q = new Node(head->val);
        cphead = head;
		/** 受判题启发：给结点编号（array-like）
		    1. 变量需要3个map，分别记录结点-编号，编号-地址/结点，结点编号-其随机结点编号
		    2. 关键问题是：随机结点是在整个链表的基础上去看，即next建立了一条完整的链表，之后才有random的关系，即random结点是已经存在的结点，不能再new了
		**/
        unordered_map<Node*, int> idxmap;
        unordered_map<int, Node*> addrmap;
        unordered_map<int, int> randomidxmap;
      
        /** 对空特殊处理（可以让idx从1开始，避开0）
        int idx = 0;

        idxmap[nullptr] = 1001;
        randomidxmap[idxmap[nullptr]] = idxmap[nullptr];
        addrmap[randomidxmap[idxmap[nullptr]]] = nullptr;
        **/
        int idx = 1;
		// 结点编号，建立新链表
        while(head){
            idxmap[head] = idx;
            idxmap[q] = idx;
            addrmap[idx] = q;

            head = head->next;
            if(head)
                q->next = new Node(head->val);
            else q->next = nullptr;
            
            q = q->next;
            idx ++;
        }
		// 记录原链表的random关系
        while(cphead){
            randomidxmap[idxmap[cphead]] = idxmap[cphead->random];
            cphead = cphead->next;
        }
        // 复刻
        while(p){
            p->random = addrmap[randomidxmap[idxmap[p]]];
            p = p->next;
        }

        return f;
    }
};
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

题解2 回溯+哈希

class Solution {
public:
    // key = 原结点
    // value = 新结点
    unordered_map<Node*, Node*> Nodemap;
    Node* copyRandomList(Node* head) {
        if(! head) return nullptr;
        // 需要克服的问题是：不知道random指向的结点是否建立过	
        // 如果没建立过，则新建
        if(! Nodemap.count(head)){
            Node* newnode = new Node(head->val);
            Nodemap[head] = newnode;
            newnode->next = copyRandomList(head->next);
            newnode->random = copyRandomList(head->random); 
        }
        
        // 建立过直接返回
        return Nodemap[head];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

哈希思路精简

class Solution {
public:
   
    Node* copyRandomList(Node* head) {
        if(! head) return nullptr;
        map<Node*, Node*> kkmap;
        Node* autohead = head;
        
        // 新建链表
        // kkmap保证每个结点对应的都是新地址
        while(autohead){
            kkmap[autohead] = new Node(autohead->val);
            autohead = autohead->next;
        }
        autohead = head;
        
        // 建立next和random关系
        while(autohead){
            kkmap[autohead]->next = kkmap[autohead->next];
            kkmap[autohead]->random = kkmap[autohead->random];
            autohead = autohead->next;
        }


        return kkmap[head];
    }
};
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

题解3 优化迭代

class Solution {
public:
   
    Node* copyRandomList(Node* head) {
        if(! head) return nullptr;
        Node* ll = head;
        Node* newhead;
        // copy to the original link
        while(ll){
            Node* nextll = ll->next;
            Node* tmp = new Node(ll->val);
            ll->next = tmp;
            tmp->next = nextll;
            ll = nextll;
        }
        // Handle random point First !!!!(next info exists)
        ll = head;
        
        while(ll){
            Node* cphead = ll->next;
            cphead->random = ll->random ? ll->random->next : nullptr;
            ll = cphead->next;
        }
		
        newhead = head->next;
        ll = head;
		// Handle next point and restore the original one
        while(ll){
            Node* cphead = ll->next;
            // 断开连接
            ll->next = cphead->next;

            cphead->next = cphead->next ? cphead->next->next : nullptr;
            ll = ll->next;
        }


        return newhead;
    }
};
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
33
34
35
36
37
38
39
40