题目

题解

链表定义：

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


详细注释看138题

1. 复制链表节点法

在每个节点后复制新的节点，三次遍历

  1. 先复制新的节点
  2. 设置新节点的random
  3. 断开原来的连接
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        auto cur = head;
        while(cur){
            auto tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }
        cur = head;
        while(cur){
            if(cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        auto res = cur->next;
        while(cur){
            auto tmp = cur->next;
            cur->next = tmp->next;
            if(tmp->next) tmp->next = tmp->next->next;
            cur = cur->next;
        }
        return res;
    }
};

2. 哈希表递归法

用一个哈希表一一对应新旧链表

class Solution {//两个方法。2. 哈希表递归法
public:
    Node* help(Node* cur, unordered_map<Node*,Node*>& m){
        if(!cur) return nullptr;
        if(m.count(cur)) return m[cur];
        auto res = new Node(cur->val);
        m[cur] = res;
        res->next = help(cur->next,m);
        res->random = help(cur->random,m);
        return res;
    }
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> m;
        return help(head, m);
    }
};