复制带随机指针的链表 - lifengyu360/lifengyu_first_git_test GitHub Wiki

给你一个长度为 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 作为传入参数。

class Solution {

public:

Node* copyRandomList(Node* head) {

    unordered_map<Node*,Node*>mp;
    mp[nullptr]=nullptr;
    auto p=head;
    while(p){
        mp[p]=new Node(p->val);
        p=p->next;
    }
    p=head;
    while(p){
        mp[p]->next=mp[p->next];
        p=p->next;
    }
    p=head;
    while(p){
        mp[p]->random=mp[p->random];
        p=p->next;
    }
    return mp[head];
}

};

class Solution

{

public:

struct Manager{
    Node* cur;//
    Node* suiji;//
};

Node* copyRandomList(Node* head) {
    //链表遍历一次可以填写下面的结构
    //第一位是序号  第二是当前节点的指针
    map<int,Manager> list_old_1;
    map<Node *,int> list_old_2; 

    map<int,Manager> list_new_1;
    map<Node *,int> list_new_2;

    if (head == NULL){
        return NULL;
    }

    Node* head_new = new Node(0);
    Node* pst = head_new;
    int i = 0;
    while(head!= NULL){
         Node* tmp = new Node(head->val);
         tmp->random = NULL;
         tmp->next = NULL;

         pst->next = tmp;
         pst = pst->next;

         Manager m_old;
         m_old.cur = head;
         m_old.suiji = head->random;

         list_old_1[i] = m_old;
         list_old_2[head] = i;
         Manager m_mew;
         m_mew.cur = tmp;//随机无法填写
         list_new_1[i] = m_mew;
         list_new_2[tmp] = i;
         head = head->next;
         i++;
    }
    
    for(int i = 0; i < list_old_1.size(); i++){
        Manager man_old = list_old_1[i];
        if (man_old.suiji == NULL){
            Manager man_new = list_new_1[i];
            man_new.cur->random = NULL;
            continue;
        }

        int suiji_xuhao = list_old_2[man_old.suiji];//指向suiji_xuhao
        
        Manager man_new = list_new_1[i];
        man_new.suiji = list_new_1[suiji_xuhao].cur;
        man_new.cur->random = man_new.suiji;
    }
   
     Node* tmp = head_new;
     head_new = head_new->next;
     delete tmp;
     return head_new;
}

};

⚠️ **GitHub.com Fallback** ⚠️