leetcode 面试150 之随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

题目重点：深拷贝，链表状态相同 

难点在于如何找到新节点的随机节点，我试过用map<int,Node*>来管理，发现有重复val值就行不通了

废话少说直接上代码

/*
// 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) {         //假设原始数据 为 1 2 3 4 
        if(head==nullptr) return nullptr;
        Node* now=head;
        
        //遍历原始链表 将其变成 1 1 2 2 3 3 4 4   此时random节点并未赋值
        while(now) 
        {
            Node* new_node=new Node(now->val);
            new_node->next=now->next;
            now->next=new_node;
            now=new_node->next;
        }
        
        //开始处理random节点   
        now=head;
        while(now)
        {
            /* 如果原始链表的随机节点不为nullptr 那我们将构造的相同节点的随机节点设置为原始随机节点的下一节点即可*/
            if(now->random!=nullptr)now->next->random=now->random->next;
            now=now->next->next;
        }

        //分离原始链表和构造链表
        now=head;
        Node* answer=new Node(0);
        Node* temp=answer;
        while(now)
        {
           temp->next=now->next;       //深拷贝链表
           temp=temp->next;
           
           now->next=now->next->next;  //原始链表
           now=now->next;
        }
        return answer->next;           
    }
};

题解还有一篇递归的解法，雀氏很nb感兴趣的可以去看看