复制带随机指针的链表
- 😉 1.题目来源
- 👀2.题目描述
- 🤔3.解题思路
- 🥳4.代码展示
所属专栏:玩转数据结构题型❤️
🚀 >博主首页:初阳785❤️
🚀 >代码托管:chuyang785❤️
🚀 >感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️
🚀 >博主也会更加的努力,创作出更优质的博文!!❤️
🚀 >关注我,关注我,关注我,重要的事情说三遍!!!!!!!!❤️
😉 1.题目来源
LeetCode:复制带随机指针的链表
👀2.题目描述
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝
。 深拷贝应该正好由 n 个全新
节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
🌟例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
🤔3.解题思路
我们分析一下题目的要求
:复制一个长度为n的链表,其中节点里面包含了一个val值和一个random随机指针,这个指针可指向链表中的任意一个节点包括了NULL。- 如果题目只是要求复制一个长度为n的链表,并且复制val值的话就简单的多了。直接遍历原链表,把值都一一复制过来就行了。但是题目多加了一个条件,就是random值。复制节点的值很简单,😔但是random是一个指向节点的指针,当我们复制链表的时候,
我们新的链表节点的地址肯定是与原链表节点的地址是不一样的
,即使遍历了原链表的random值也找不到新链表的random值,🙅 所以找到random值是一个难点。 - 那既然这样我们便可以创建一个
长度为n+1的整形数组
,用来记录每个节点距离头节点的距离包括了NULL
。这样的话我们就可以先遍历原链表,把每个节点random所指向的值计入到数组当中,然后复制链表的时候,🤩根据这个数组来找到random指向的值。这固然是一种方法,但是他的空间复杂度:O(n)
,时间复杂度:O(n^2)
,并不是一个好的解题方法。 - 🤔那怎么才可以在遍历原数组的过程中就可以确定复制链表的random值呢?那我们就可以从原链表出发。🤯于是我们就想到了,如果我们把每个要复制的节点都插入到被复制节点的后面(也就是每个原节点的后面)这样的话,就很好的解决了找random值这一问题。我们原节点->random->next == 复制节点->random。
- 完成复制与以及给random赋值完后,就可以把复制节点断开,一一链接成链表,并且恢复原链表
🥳4.代码展示
struct Node* copyRandomList(struct Node* head)
{//第一步,把每个拷贝节点链接到原节点出struct Node* cur = head;while (cur){struct Node* Next = cur->next;//开辟赋值节点struct Node* copyNode = (struct Node*)malloc(sizeof(struct Node));//给节点拷贝val值copyNode->val = cur->val;cur->next = copyNode;copyNode->next = Next;cur = Next;}//第二步,给random赋值cur = head;while (cur){struct Node* copyNode = cur->next;if (cur->random == NULL){copyNode->random = NULL;}else{copyNode->random = cur->random->next;}cur = copyNode->next;}//第三步,链接赋值链表,并恢复原链表cur = head;struct Node* copyhead = NULL, *copyCur = NULL;while (cur){struct Node* copy = cur->next;struct Node* Next = copy->next;if (copyhead == NULL){copyhead = copyCur = copy;}else{copyCur->next = copy;copyCur = copyCur->next;}cur->next = Next;cur = Next;}return copyhead;}