题目

题解

链表定义：

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

1. 复制链表节点法

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

  1. 先复制新的节点
  2. 设置新节点的random
  3. 断开原来的连接
class Solution {//两种方法。1、复制链表法。三次遍历，时间O(n)，空间O(1)
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;//设置边界条件，一般没有哑节点就用这个
        Node* cur = head;//设置指针用于遍历
        while(cur){//第一次遍历在每个节点后复制一个节点作为新节点,并进行连接操作
            Node* t = new Node(cur->val);
            t->next = cur->next;
            cur->next = t;
            cur = t->next;
        }
        cur = head;//将cur放回开头，准备第二次遍历，这一次进行random指针设定
        while(cur){
            if(cur->random)cur->next->random = cur->random->next;
            //这句重点理解，可以看题解的图，注意random有可能为NULL，因此要加判断
            cur = cur->next->next;
        }
        cur = head;//最后一次cur回到开头，准备第三次遍历，这次将原链表与拷贝链表分开
        Node* res = head->next;
        //注意要在这里加一个用于返回的节点，进行完下一次遍历后面就断开了，没法设置了
        while(cur){
        //注意这里也要用一个中间节点t，因为直接用cur的话每次连接完会断开一个未遍历的原节点
            Node* t = cur->next;
            cur->next = t->next;
            if(t->next)t->next = t->next->next;//注意这里也要加判断，防止有空指针
            cur = cur->next;
        }
        return res;
    }
};

2. 哈希递归法

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

class Solution {//两种方法。2、哈希表递归法，创建一个哈希表用于一一对应原链表与新链表的关系
                //递归的方式更简洁，不用遍历两次
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> m;//设置上述的哈希表
        return helper(head,m);
    }

    Node* helper(Node* cur, unordered_map<Node*, Node*>& m){
        if(!cur) return NULL;//若这个节点为空，则直接返回空，对于头节点head也适用
        if(m.count(cur)) return m[cur];//若哈希表已经有对应值了，则直接返回哈希表的对应值
        Node* res = new Node(cur->val);//若哈希表中没有，则创建一个新的节点
        m[cur] = res;//将新节点与原节点通过哈希表进行关联
        res->random = helper(cur->random,m);//通过递归确定新节点的next和random
        res->next = helper(cur->next,m);
        return res;//返回该新节点
    }
};