染念的笔记

复制，就需要和原链表的地址不同，不能引用原地址，因此你需要开辟新的空间。正常情况下，你只需要遍历下面，但现在是复杂链表，random 指向任意的节点，所以如果你只是遍历多次，你可能遇到指向的节点，在遍历时候还没有创建，或者创建成功了，每次去查找它，让时间复杂度何其复杂，所以我们要存储节点 这里，介绍两种方法

法 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 == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        while(cur != nullptr){
             map[cur] = new Node(cur->val);
             cur=cur->next;
         }
         cur = head;
         while(cur !=nullptr){
             map[cur]->next = map[cur->next];
             map[cur]->random = map[cur->random];
             cur = cur->next;
         }
         return map[head];
    }
};

解析：按实例，如果节点为空，直接输出 null。 c++使用哈希表借助 unordered_map, 我们先通过遍历创建哈希表，例如，map[A] = A* 这里的 A 是指链表指针的原地址，A*注意了，是你重新开辟的值为 A 的节点！因为是复制，所以不能引用原地址。然后再给新节点 random 和 next 指针引用新节点。这里的循环依旧通过原地址去映射找出新节点。我这里，一开始的想法是：

map[cur]->next = cur->next;
map[cur]->random = cur->random;

实际上，又引用了原节点，是错的，大家应该避免。

方法，拼接和拆分 #

原链表为，A->B->C 那我们就要创建A->A->B->B->C->C... 然后再把新创建的节点分离开，另一种存储节点的方式就是直接作用在原链表上，空间复杂度随之减少了。

/*
// 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 == nullptr) return nullptr;
        Node* cur = head;
        // 复制新节点拼接，这里建议大家画图，能够更加清楚认识。
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        cur = head;
        // 给新节点random和next指向，注意，你指向的需要是新节点，是next的next
        while(cur != nullptr){
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 拆分
        Node* pre = head,*res = head->next;
        cur = head->next;
        while(cur->next!=nullptr){
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
       // 这里只是为了完整，把原链表分离出来，最后指向null，而为什么新链表不用指了呢？
       // 因为新链表用了原链表最后的null，在前面的创建中，新节点->null
        pre->next = nullptr;
        return res;
    }
};

这里还要讨论两个 while 循环，为什么一个是判断cur!=nullptr,而另一个却是cur->next

起始点不一样，第一个是 head，第二个是 head->next 因为复制在原链表的原因，旧节点后面必然接着新节点，所以 cur 的 next 必然有，如果 cur 是 null，那自然不需要了。后面我们在分离，我们就要知道，实际我们判断的是 cur/head 的 next 的 next，新链表最后必接了 null，所以这样不会造成 next 的 next，nul 的 next 还是 null 的错误了。