138. Copy List with Random Pointer.md

138. Copy List with Random Pointer

思路

题目要求深拷贝一个链表，难点就在于如何处理随机指针的问题。

思路一

可以先不管random指针，遍历一遍链表并进行拷贝，同时用一个HashMap记录节点与其副本的隐射关系。第二次遍历再处理random指针。

思路二

也可以采用DFS的思路进行递归拷贝，这样就和133. Clone Graph拷贝图中的DFS解法很类似了。

思路三*

前两种方法都需要开辟一个HashMap，如果不允许额外开辟空间呢？

我们开辟HashMap的目的是在处理副本节点的random指针时能够快速定位原节点random指向的节点的副本节点，即原节点到副本节点的映射。那如果我们一开始复制节点的时候将副本节点插入到原节点后面不就实现了原节点到副本节点的映射了吗。

我们可以遍历一遍链表，然后将每个节点后紧接上其对应副本节点（同样是先不管副本节点的random指针），遍历完成后即变成

原链表（省略random，下同）:
1 -> 2 -> 3.
将每个节点后接上其对应副本节点:
1 -> 1' -> 2 -> 2' -> 3 -> 3'.

然后再遍历一遍处理副本节点的random指针，最后将新的链表拆成新旧两个部分即可。即一共有三个步骤：

1. 复制节点并紧接在源节点后面；
2. 处理random指针
3. 拆分成两个链表

这样就不用开辟额外的空间了，完美。

C++

思路一

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        unordered_map<Node*, Node*>mp;
        Node *head_cp = new Node(head -> val);
        mp[head] = head_cp;
        Node *p1 = head_cp, *p2 = head -> next;
        while(p2){
            p1 -> next = new Node(p2 -> val);
            mp[p2] = p1 -> next;

            p1 = p1 -> next; p2 = p2 -> next;
        }
        p1 -> next = NULL;
        
        p1 = head_cp; p2 = head;
        while(p2){
            p1 -> random = mp[p2 -> random];
            p1 = p1 -> next; p2 = p2 -> next;
        }
        
        return head_cp;
        
    }
};

思路二

class Solution {
private:
    Node* DFS(Node *node, unordered_map<Node*, Node *>&mp){
        if(!node) return NULL;
        if(mp.count(node)) return mp[node];
        else{
            Node *node_cp = new Node(node -> val);
            mp[node] = node_cp;
            node_cp -> next = DFS(node -> next, mp);
            node_cp -> random = DFS(node -> random, mp);
            return node_cp;
        }
    }
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        unordered_map<Node*, Node*>mp;
        return DFS(head, mp);
        
    }
};

思路三*

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        Node *cur = head;
        
        // 1.复制节点并紧接在源节点后面
        while (cur) {
            Node *t = new Node(cur->val, NULL, NULL);
            t->next = cur->next;
            cur->next = t;
            cur = t->next;
        }
        
        // 2. 处理random指针
        cur = head;
        while (cur) {
            if (cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        
        // 3. 拆分成两个链表
        cur = head;
        Node *res = head->next;
        while (cur) {
            Node *t = cur->next;
            cur->next = t->next;
            if (t->next) t->next = t->next->next;
            cur = cur->next;
        }
        return res;
    }
};