文章目录
- 🍇前言
- 🍎复制带随机指针的链表
- 🍑写在最后
🍇前言
-
本章的链表
OJ
练习,是最后的也是最难的。对于本题,我们不仅要学会解题的思路,还要能够通过这个思路正确的写出代码,也就是思路转化为代码的过程,这应该就是最难的地方了吧。 -
对于OJ练习(5): -> 传送门 <-,环形链表的做法的证明一定要理解透彻,因为面试很可能问到噢。
🍎复制带随机指针的链表
-
题目链接:-> 传送门 <-。
-
题目描述:给你一个长度为
n
的链表,每个节点包含一个额外增加的随机指针random
,该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由n
个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的next
指针和random
指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如:如果原链表中有X
和Y
两个节点,其中X.random --> Y
。那么在复制链表中对应的两个节点x
和y
,同样有x.random --> y
。返回复制链表的头节点。 -
也就是复制一个链表。
例如复制下面这个链表:(复制后返回复制后的链表的头节点)
解题思路:
-
我相信,看到这个题,第一感觉就是暴力把他给复制了。但暴力终会达到
O(N^2)
,虽然可以过,但如果面试的时候遇到这个问题,面试官可能就会问:如何将时间复杂度降到O(N)
呢? -
所以这里使用一种
O(N)
的方法来解这道题。 -
首先,我们在原链表上的每一个节点后面插入一个与自己有相同值的节点(称为
copy
节点),然后进行连接,如下:
- 然后进行的操作是最关键的:再遍历一遍连接了
copy
节点后的链表,将每一个copy
节点的random
指向它前一个节点(就是被复制的那个节点,因此这里操作的时候,需要一个指针指向copy
节点的前一个节点)的random
的next
节点,如果copy
的前一个节点的random
指向NULL
,那直接将copy
节点的random
指向NULL
,直到遍历结束,可以得到下面这个链表:
-
细心观察不难发现,上面的所有
copy
节点组成的链表实际上就与原链表相同了。 -
因此最后的操作,就是将每一个
copy
节点取下来尾插到新的链表上,最后返回这个新链表的头即可。当然啦,这里还需要将原链表复原。 -
根据上面的思路,会发现,如何将这些过程转换成代码是个难点。这里没得巧,就是多练,多写,正如:无他,唯手熟尔。
⏩下面是代码实现(注意:一边写代码或者看代码,一边要体会整个思路的过程):
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
while (cur)
{
// 创建copy节点
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
// 存放当前节点的下一个节点的地址,便于连接和继续遍历链表
struct Node* next = cur->next;
// 连接
cur->next = copy;
copy->next = next;
cur = next;
}
cur = head;
while (cur)
{
// 同样三个指针遍历
struct Node* copy = cur->next;
struct Node* next = copy->next;
// 放置copy的random指针
if (cur->random == NULL) copy->random = NULL;
else copy->random = cur->random->next;
cur = next;
}
// 新链表的头和连接新链表的指针
struct Node* copyHead = NULL, *copyTail = NULL;
cur = head;
while (cur)
{
// 同样需要三个指针来遍历
struct Node* copy = cur->next;
struct Node* next = copy->next;
// 如果copyHead为NULL,先同时指向头节点
if (copyHead == NULL)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
// 复原原链表
cur->next = next;
// 找下一个
cur = next;
}
return copyHead;
}
🍑写在最后
对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。单链表的OJ练习在此就结束了,大家要好好练习噢~
感谢阅读本小白的博客,错误的地方请严厉指出噢~