[LeeCode 138]复制带随机指针的链表

[LeeCode 138] C++实现复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。
每个节点用一个 [val, random_index] 表示：
-----val：一个表示 Node.val 的整数。
-----random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

来源：力扣（LeetCode 138）
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer

//方法1、 哈希
class Solution {
public:
    Node* copyRandomList(Node* head){
        if(!head)
            return nullptr;
        map<Node*,Node*>mp;//原链表节点与对应位置的新链表节点
        Node* ptr=head;
        while(ptr){
            Node* temp=new Node(ptr->val);//新链表节点
            mp[ptr]=temp;//建立映射关系
            ptr=ptr->next;//遍历
        }
        ptr=head;
        while(ptr){
            Node* newNode=mp[ptr];
            newNode->next=mp[ptr->next];//根据map连接新链表
            newNode->random=mp[ptr->random];
            ptr=ptr->next; //遍历原链表           
        }
        //ptr指向链表尾部
        return mp[head];//返回首部节点
    }
};

//方法2、map+vector 
//不推荐
class Solution {
public:
Node* copyRandomList(Node* head) {
         map<Node*,int>node_M;
        vector<Node*>node_V;
        int i=0;
        Node* ptr=head;
        
        while(ptr){
            //遍历原始链表
            //Node* temp=new Node(ptr->val);
            node_V.push_back(new Node(ptr->val));//vector中传入新链表
            node_M[ptr]=i;
            ptr=ptr->next;
            ++i;//记录节点位置
        }

        node_V.push_back(0);
        ptr=head;
        i=0;

        while(ptr){
            node_V[i]->next=node_V[i+1];
            if(ptr->random){
                int id=node_M[ptr->random];
                node_V[i]->random=node_V[id];
            }
            ptr=ptr->next;
            ++i;
        }
        return node_V[0];
    }
};