LeetCode Copy List with Random Pointer 分析解答

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

首先搞清楚什么是浅拷贝和深拷贝：

浅拷贝，把一个变量中的数据地址直接给另一个变量，删除其中任何一个变量，另一个变量中就没有了地址数据。

深拷贝，创建一个新的空间保存这个变量的值，所以，当删除任何一个变量时，就不会出错，因为它们的地址不同

如下列：

 

#include <iostream>  
#include <cstdlib>  
#include <memory>  
int main()  
 {  
         int* p1 = new int(1);  
           
         std::auto_ptr<int> p(new int(*pInt) );  
         int* p2 = p.get();  
             
         delete p1;                                                                                                  
         std::cout<<*p2<<std::endl;                                                                                                                                                                                                                                                                                                              
         system("PAUSE");   
         return 0;  
 }   

 

 

 

下面是用map来写的一个程序，第一次提交就通过了，暗暗高兴中。

 

/** 
 * Definition for singly-linked list with a random pointer. 
 * struct RandomListNode { 
 *     int label; 
 *     RandomListNode *next, *random; 
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    RandomListNode *copyRandomList(RandomListNode *head)   
    {  
        if(head == nullptr) return nullptr;  
        map<RandomListNode *, RandomListNode *> nodesmap;  
        nodesmap = copyList(head);  
        randomPtr(nodesmap);  
        return nodesmap[head];  
    }  
  
    map<RandomListNode *, RandomListNode*> copyList(RandomListNode *head)  
    {  
        RandomListNode * node = head;  
        map<RandomListNode *, RandomListNode*> nodesmap;  
        RandomListNode *chead = new RandomListNode(*node);  
        nodesmap[node] = chead;  
        RandomListNode *cur = chead;  
        while (node->next != nullptr)  
        {  
            RandomListNode *ctemp = new RandomListNode(*(node->next));  
            nodesmap[node->next] = ctemp;  
            cur->next = ctemp;  
            cur = ctemp;  
            node = node->next;  
        }  
        cur->next = nullptr;  
        return nodesmap;  
    }  
  
    void randomPtr(map<RandomListNode *, RandomListNode*> &nodesmap)  
    {  
        auto iter = nodesmap.begin();  
        for(; iter != nodesmap.end(); iter++)  
        {  
            iter->second->random = nodesmap[iter->first->random];  
        }  
    }  
};  

 

 

补充：软件开发 , C++ ,