【数据结构与算法】leetcode随机链表的复制 深度讲解

随机链表的复制

   小编个人主页详情<—请点击
小编个人gitee代码仓库<—请点击
数据结构与算法系列专栏<—请点击

  
  
一、标题解读

   查看原题请点击<—

  

• 该标题的随机链表与我们常规的单链表的构造不同，单链表的讲解请点击<—，除了有指向下一个节点的指针外，还有一个指针可以指向该链表的恣意位置包括空NULL
  
• 标题要求我们复制一份随机链表，并且复制的新的链表的随机指向的指针应该指向我们本身复制的节点，不可以或许指向原随机链表
  

---

二、解题思路

在了解标题要求之后，那么我们就可以来举行构思这个标题的思路了
三种猜想思路

思路一

• 标题让我们复制一份随机链表，先抛开随机，那么我们可以先构造一份链表，节点个数等于原随机链表，并且其中存放的val值等于原链表的值，next指针和原随即链表一样指向下一个节点
  
  
  
  
• 那么在构造完成后，余下的随机指针应该怎样举行构造存储呢？
  
• 有的读者朋侪们会想，这简朴，遍历原随机链表，将原随机链表中存储的随机链表的随机指针的值拷贝到我们的复制链表中的随机指针不就好了吗，这里小编想说想法固然美好的，可是现实却是残酷的
  
• 这个标题要求咱们新构造的复制链表不能和原随机链表有任何的指向关系，这个样子举行复制可不就将咱们构造好的复制链表中的随机指针指向的原随机链表中的节点了嘛，以是这种方法不可取
  

思路二

• 那么我们应该怎样根据原随机链表的随即指针举行构造复制链表中的随机指针呢？
  
• 有的读者朋侪会想，这简朴，我根据随机指针指向的节点中存储的val值举行查找存储不就好了，根据上图来看，大概这种方法可以。倘若小编给你下面这个图呢？是不是就无法举行查找了
  
  
  
  

思路三

• 那么我们应该怎样根据原随机链表的随即指针举行构造复制链表中的随机指针呢？
  
• 有的读者朋侪大概会有这样的想法，开两个指针数组，分别将原随机链表中的节点的地址按顺序逐个举行传入，再将复制链表中的单个地址举行逐个传入
  
• 遍历原随机链表和复制链表，将原随即链表中随机指针的值在指针数组中举行查找，并且记载下指针数组的下标
  
• 根据指针数组下标我们去对应的另一个复制链表的数组下标所存储的指针地址的值，将其赋值给复制链表中节点对应原随机链表位置的随机指针即可
  

   

  

• 但是这种开辟指针数组的这种方法时间复杂度较大为O(N^2)，开辟两个指针数组遍历为O(N)，寻找原随即链表中随机指针的值时间复杂度为O(N),找到的数组下标对应到复制链表对应的指针数组时间复杂度为O(1),完成1个随机指针的查找复制的时间复杂度O(2N)
  
• 有N个数据需要查找N次，时间复杂度为O(（2N）*N)，省略常数2，则时间复杂度为O(N^2)
  

   那么有没有一种方法时间复杂度为O(N)呢？有的有的，请看小编下面文章，真正的思路讲解
  真正的解题思路

1.构建重组链表

• 既然在其他位置举行构造复制链表行不通，那么我们是否可以在原随机链表的每个节点背面举行构建复制链表节点，找到随机指针，最后再断开和复原呢？完全有大概
  
• 我们利用cur节点遍历随机链表，利用malloc开辟节点newnode，放入cur的val值，按照下图方式举行cur和newnode的链接
  
• 当cur遍历到空的时候，我们就初步构建好了
  

2.寻找复制链表的随机指针并赋值

• 观察，随机链表中值为13的节点的下一个节点恰好为我们构建的复制链表中的13
  
• 观察我们构建的新链表，比方随机链表中值为13的节点的中的随机指针指向随机链表7的节点
  
• 再观察，随机链表中的值为13节点的随机指针指向的随机链表7的节点的背面恰好就为我们的复制链表的13的节点所要找的复制链表对应的本身的随机指针指向所应该要找的位置
  
• 这样就可以依附位置关系找到复制链表对应的随机指针的地址举行寻找并存储
  
• 留意当随机链表中的随即指针为空的之后要特别处理，对应下一个节点的复制链表中的随机指针应该也为空
  
• 利用cur遍历重构链表，并且利用copy节点保存cur的下一个位置的地址
  
  
  
  
• 寻找cur的随机指针random的下一个节点就为要找寻的复制链表对应的随机指针的位置，存储到复制链表中的随机指针random即可
  
• 当cur遍历到空的时候，我们的复制链表的随机指针赋值完成
  

3.复原随机链表和复制链表

• 当我们将复制链表中的随机指针都找到对应位置并且赋值为对应位置的指针之后，应该做出复原操作
  
• 复制操作即利用循环将复制链表的节点按顺序链接起来，将随机链表的节点按顺序链接起来即可
  
• 界说newnode和tail节点，举行复制链表的尾插
  
• 界说cur作为第一个节点，copy为第二个，next为第三个节点
  
  
  
  
• cur和next用于链接随机链表，copy和newhead和tail用于链接复制链表，将newhead和tail举行赋值为NULL野指针和非法访问内存
  
• 将cur的存储的下一个节点的指针指向next，这是对随机链表的节点复原
  
• 将copy的节点利用tail指针尾插到newhead中，这里留意由于最初的时候newhead和tail举行赋值为了NULL，以是第一次的时候应该采用将copy节点赋值给这newhead和tail才能举行后续的操作
  
• 这里的newhead是作为复制链表的头举行返回，tail作为尾节点举行尾插copy节点操作
  
• 当cur遍历到空的时候，我们的复原操作完成，返回复制链表的头节点newhead即可
  

   

    好了到这里，小编信赖屏幕眼前的你已经对这个标题的思路大要了解了，点击链接实验做一下吧查看原题请点击<—
  

---

三、编写代码

下面即为该题的代码

1. /**
2. * Definition for a Node.
3. * struct Node {
4. *     int val;
5. *     struct Node *next;
6. *     struct Node *random;
7. * };
8. */
10. struct Node* copyRandomList(struct Node* head) {
11.     //构造复杂链表链接到随机链表节点后面
12.         struct Node* cur=head;
13.     while(cur)
14.     {
15.         struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
16.         struct Node* next=cur->next;
17.         newnode->val=cur->val;
18.         //链接
19.         cur->next=newnode;
20.         newnode->next=next;
21.         //迭代
22.         cur=next;
23.     }
25.     //赋值随机指针
26.     cur=head;
27.     while(cur)
28.     {
29.         struct Node* copy=cur->next;
30.         //链接
31.         if(cur->random==NULL)
32.         {
33.             copy->random=NULL;
34.         }
35.         else
36.         {
37.             copy->random=cur->random->next;
38.         }
39.         //迭代
40.         cur=copy->next;
41.     }
43.     //复原
44.     struct Node* newhead,*tail;
45.     newhead=tail=NULL;
46.     cur=head;
47.     while(cur)
48.     {
49.         struct Node* copy=cur->next;
50.         struct Node* next=copy->next;//对copy和next根据cur进行初始化
52.         cur->next=next;
53.         if(newhead==NULL)
54.         {
55.             newhead=tail=copy;
56.         }
57.         else
58.         {
59.             tail->next=copy;
60.             tail=copy;
61.         }
63.         cur=next;
64.     }
66.     return newhead;
67. }

复制代码

总结

   以上就是今天的博客内容啦,水滴石穿，坚持就是胜利，读者朋侪们可以点个关注
点赞收藏加关注，关注小编的后续更新！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。