• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

算法基础~链表~复杂链表(带有随机指针的链表)深度拷贝

开发技术 开发技术 4小时前 1次浏览

算法基础~链表~复杂链表(带有随机指针的链表)深度拷贝

1,复杂链表图解:

算法基础~链表~复杂链表(带有随机指针的链表)深度拷贝

2,第一印象思路:若是没有随机指针的标志的话,则简单啦。

知识点:指针指向~地址【结点地址】

 

3,本题难点:因为随机指针的指向而使得链表变得复杂无序化~~~~

~解决:无序化,则有序化呀,找出规律!

(将结点有序化~将结点所在地址“有序化”~~编号id,这样的话,随机指针指向边有“id编号”)

4,id编号化结点位置图解:

算法基础~链表~复杂链表(带有随机指针的链表)深度拷贝

5,过程:第一个结点位置 id = 0;    第二个结点位置 id = 1;   第三个结点位置 id = 2;

                第四个结点位置 id = 3;  第五个结点位置 id = 4; 第六个结点位置 id = 5;

【结点位置    id】    这是一种映射呀宝贝,so, map 结构~【结点位置,id】

 

6,在这样一番“有序化”操作后,看图,“第一个结点(id = 0)的随机指针指向 id = 2 的结点。”~“有序化”~

~联想到 List(有序)的存储结构我们使用的是List 的子类vector。  第一个结点(id = 0)的随机指针指向 id = 2 的结点。”~

~则用vector表达为:vector[0]->random = vector[2].

 

7,直接上代码,分析过程如上:

ps:代码中定义了一个辅助指针 ptr,作用是因为原链表需要被遍历两次,如果只遍历一次的话,头指针移动就够了,so,遍历两次原链表,

加了一个辅助指针,而头指针不动,才能回头第一个结点

public class Solution {
  public:
    RandomListNode *copyRandomList(RandomListNode *head){
        std::map<RandomListNode *, int> node_map;
        std::vector<RandomListNode *> node_vector;
        RandomListNode *ptr = head;
        int i = 0;
        while(ptr){
            //vector依次元素装上原链表的结点
            node_vector.push_back(new RandomListNode(ptr->label));
            //初始化map集合,构建【结点位置,id】
            node_map[ptr] = i;
            ptr = ptr->next;
            i++;
        }
        node_vector.push_back(0);
        //ptr指针回到原链表第一个结点
        ptr = head;
        i = 0;
        //把vector中的结点连在一起成一条链,并且同时随机指针的指向标志好
        while(ptr){
            node_vector[i]->next = node_vecotr[i + 1];
            if(ptr->random){
                int id = node_map[ptr->random];
                node_vector[i]->random = node_vector[id];
            }
            ptr = ptr->next;
            i++;
        }
        return node_vector[0];
  }
}

 

 

 

 

 

 

喜欢 (0)