leetcode刷题05--复杂的链表的深度拷贝--T138

题目:

image.png

---

深度拷贝:
构造一个完全新的链表,即使将原链表毁坏,新链表也可以独立使用

自己的思路:
无....

好吧看一下ppt的思路:
ppt中的解法,利用到了stl中的map:
知识补充:

std::map

image.png

map是一种映射的数据格式
在这里可以将链表节点地址作为map序号,其映射值为该地址对应的链表节点序列

该工具足矣解决该问题的难点:
如何在新链表中保留旧链表random指针所指向的相对位置

std::vector

vector(向量):是一种顺序容器，事实上和数组差不多，但它比数组更优越。一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界。而vector正好弥补了这个缺陷，它的特征是相当于可分配拓展的数组，它的随机访问快，在中间插入和删除慢，但在末端插入和删除快。

思路:

用一个map,存放原链表的序号和地址的映射关系,和一个vector,存放存放新链表的序号和地址的映射关系
之所以不用两个map,是由于新链表要通过序号找地址;当然,用一个结构和前者相反的map也可以,不过有些不好用
所以可以得到每个原链表节点的random指针所指向的节点的序号,并应用在新链表中:
head_new->random = vector[map[head.random]]

image.png

---

代码:

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //创建一个map和一个vector
        std::map<Node*, int> node_map;
        //vector同时也用来存放新的链表
        std::vector<Node*> node_vec;
        //指向起始节点
        Node* ptr = head;
        //记录序号
        int i = 0;
        //遍历原链表,将结构存入map中
        while(ptr){
            //同时创建新链表节点
            node_vec.push_back(new Node(ptr->val,NULL,NULL)); 
            //确定映射关系
            node_map[ptr] = i;
            //指向下一个
            ptr = ptr->next;
            i++;
        }
        //将尾节点置0是让其不需要特殊化处理尾节点  0为空?
        node_vec.push_back(0);
        ptr = head;
        i = 0;
        //将原链表中random的关系迁移到新链表中
        while(ptr){
            //链表关系
            node_vec[i]->next = node_vec[i+1];
            //random不为空才记录
            if(ptr->random){
                //random关系
                //id = node_map[ptr->random]
                 node_vec[i]->random = node_vec[node_map[ptr->random]];
            }
            ptr = ptr->next;
            i++;
            
        }
        return node_vec[0];
        
    }
};

---

总结:
今天写的不好,效率不够高,花了1个多小时做这个,而且主要的时间被浪费到了琐事之上,引以为戒!