138.复制带随机指针的链表

138. 复制带随机指针的链表

题目描述：

一个长度为 $ n $ 的链表head，每个节点有一个random指针域，指向链表中的任何节点或空节点。

构造该链表的深拷贝。深拷贝的链接关系与原链表相同，但节点全是新节点。

数据范围：
$ 0\le n \le 1000 $

题解：

如果是java或者python比较简单，因为内置的map可以处理任意类型。直接将原链表的node映射到新node。然后遍历一遍原链表，同时构建新链表的映射关系。

但是c++的话，内置unordered_map不能hash非基础类型，因此需要使用其他方法。

1. 首先遍历原链表，为每个节点创建一个拷贝，挂在原节点的后面。A->A'->B->B'
2. 这样的话，再次遍历，就可以轻松得到新链表random域的映射关系。A'->random = A->random->next
3. 再次遍历，将新链表与原链表分离。

使用空的头节点可以简化编程。

代码：

/*
// 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:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    Node *copyRandomList(Node *head)
    {
        if (head == nullptr)
            return nullptr;
        Node *vir_head = new Node(0);
        vir_head->next = head;
        Node *cur = vir_head->next;
        while (cur)
        {
            Node *cur_next = new Node(cur->val);
            cur_next->val = cur->val;
            cur_next->random = cur->random;
            cur_next->next = cur->next;
            cur->next = cur_next;
            cur = cur->next->next;
        }
        cur = vir_head->next->next;
        while (cur)
        {
            if (cur->random != nullptr)
            {
                cur->random = cur->random->next;
            }
            if (cur->next == nullptr)
                break;

            cur = cur->next->next;
        }
        cur = vir_head->next;
        Node *tail = vir_head;
        while (cur)
        {
            tail->next = cur->next;
            tail = cur->next;
            
            cur->next = cur->next->next;
            cur = cur->next;
        }
        return vir_head->next;
    }
};