LeetCode-学会复杂带随机指针链表的题(详解)

前言

😂这方法太棒了!

一、复杂带随机指针链表题链接

题目描述

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
LeetCode-学会复杂带随机指针链表的题(详解)

构造这个链表的 深拷贝

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

测试样例1
LeetCode-学会复杂带随机指针链表的题(详解)

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

测试样例2:自己指向直接
LeetCode-学会复杂带随机指针链表的题(详解)

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

测试样例3:val全相同
LeetCode-学会复杂带随机指针链表的题(详解)

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

测试样例4:为空

输入:head = []
输出:NULL

题目思路

  1. 对于链表,最好的方法就是开辟空间
  2. 除了空,其他节点都另外开辟一个空间,来重新连接这个链表
    LeetCode-学会复杂带随机指针链表的题(详解)
  3. 然后通过原链表节点的random的指向来连接新开辟中random的关系
    LeetCode-学会复杂带随机指针链表的题(详解)
    4.最后来连接 开辟的新节点,重新连接老链表

注意:头节点为空的时候

代码如下

struct Node* copyRandomList(struct Node* head)  {      if(head==NULL)     return NULL;  	//开辟空间     struct Node*copy=NULL;     struct Node*cur=head;     while(cur)     {         struct Node*next=cur->next;         copy=(struct Node*)malloc(sizeof(struct Node));         copy->val = cur->val;         copy->next=next;         cur->next=copy;         cur=next;     }     cur=head;     copy=cur->next;     while(cur)     {         copy=cur->next;         if(cur->random!=NULL)         {             copy->random=cur->random->next;         }           else         {             copy->random=cur->random;         }         cur=copy->next;     }     //链接random     struct Node*guardHead=NULL;     struct Node*guardTail=NULL;     struct Node*liberate=NULL;     guardTail=guardHead=liberate=(struct Node*)malloc(sizeof(struct Node));     cur=head;     while(cur)     {         copy=cur->next;          cur->next=copy->next;          guardTail->next=copy;          guardTail=copy;          cur=copy->next;      }     guardHead=guardHead->next;     free(liberate);     return guardHead;  } 

总结

🤣就是玩!

版权声明:玥玥 发表于 2021-04-14 21:10:01。
转载请注明:LeetCode-学会复杂带随机指针链表的题(详解) | 女黑客导航