复制带随机指针的链表

给你一个长度为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.复制带随机指针的链表

什么鬼题目把一个深拷贝说得又臭又长

哈希表

可以用哈希表，旧节点映射到新节点。先用哈希表把所有节点抄下来，然后再遍历一次加上next和random指针。

/*
// 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) {
        unordered_map<Node*, Node*> nodeMap;
        Node* curr = head;
        while(curr){
            nodeMap[curr] = new Node(curr->val);
            curr = curr->next;
        }
        curr = head;
        while(curr){
            nodeMap[curr]->next = nodeMap[curr->next];
            nodeMap[curr]->random = nodeMap[curr->random];
            curr = curr->next;
        }
        return nodeMap[head];
    }
};

原地拷贝

当然也可以不用哈希表，直接在原来的指针后面new上一个一模一样的跟屁虫指针，也能实现类似哈希表的功能。也就是原指针的next就是映射的新指针，只是遍历的时候记得两个两个地遍历。

还有原来的链表也要恢复原样哦！还有对于头指针为空的特判哦！

/*
// 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* curr = head;
        while(curr){
            Node* newNode = new Node(curr->val);
            newNode->next = curr->next;
            curr->next = newNode;
            curr = curr->next->next;
        }
        curr = head;
        while(curr){
            curr->next->random = curr->random? curr->random->next : nullptr;
            curr = curr->next->next;
        }
        Node* newHead = head->next;
        curr = head;
        Node* newCurr = newHead;
        while(curr && newCurr){
            curr->next = newCurr ? newCurr->next : nullptr;
            newCurr->next = newCurr->next ? newCurr->next->next : nullptr;
            curr = curr->next;
            newCurr = newCurr->next;
        }
        return newHead;
    }
};