做完了一些较为基础的题目后,会不会发现链表题目其实只要把图给画好了,逻辑理清晰,一切就会迎刃而解。如果有这种感觉的话,不妨来挑战一下下面这道来源于力扣上的一道题目:https://leetcode.cn/problems/copy-list-with-random-pointer(点击传送) 如下:
给你一个长度为 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 作为传入参数。
分析: 这道题首先看到的第一感觉就是,哎呀我去,这么长的题目,让人眼花缭乱的,但其实这么多文字,我们根据底下的案例,提取关键因素就会发现,无非就是将原有链表给复制一份,同时原有链表的random指针是随机指向某一个节点的,复制链表的同时也要保证该节点的random指针指向的值与原有链表的random指向的值不变。
理解题目要求后我们该考虑应如何入手,这里有一种比较好的思路如下: 1、我们先将原有链表的每个节点都拷贝一份放在原节点的后面。如下:
2、我们发现,原节点的random随机指向的元素它的后面就是自己的拷贝节点,这说明了什么呢?我们第一步并没有处理random指针,但是我们可以发现,假如我们用cur遍历原链表,用tail遍历复制后的节点,cur->random->next节点,就是tail的random要找的节点。
就比如说,13的random是7,copy13的random就应该是7的next。 这样就保证了我们利用该规律可以使复制后的节点的random指向它应属于的位置。即,我们根据原链表的random指向的节点的下一个节点,就可以确定复制后的random应指向的节点。(空指针情况另行处理)
3、到了第三步,我们的复制后的链表节点的random已经处理完毕了,接下来我们将两个链表分割开来即可。
(图画的有点乱,大家自行根据分析或者后面的代码理解后去画图会很好理解)
最后便是代码的实现(一定要理清思路后再写,多画图):
struct Node* copyRandomList(struct Node* head) {
//1、先将原链表的节点拷贝并连接在原节点后面
struct Node*cur=head;
while(cur)
{
//malloc拷贝的新节点
struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
struct Node*next=cur->next;
//将值放入拷贝的节点
copy->val=cur->val;
//连接所有节点
cur->next=copy;
copy->next=next;
cur=next;
}
//处理随机指针
//cur从head遍历,步长为2(即按照原链表进行遍历)
cur=head;
while(cur)
{
struct Node*tail=cur->next;
struct Node*next=tail->next;
//random不为空,根据原链表的random指向的节点的next来找到复制后的random指向的节点
if(cur->random!=NULL)
{
tail->random=cur->random->next;
}
//为空直接置空
else
{
tail->random=cur->random=NULL;
}
//cur步长为2
cur=next;
}
//分割链表(哨兵卫)
struct Node*newhead=(struct Node*)malloc(sizeof(struct Node));
newhead->next=NULL;
struct Node*tail=newhead;
//cur从head遍历,步长为2(即按照原链表进行遍历)
cur=head;
while(cur)
{
struct Node*next=cur->next;
tail->next=next;
tail=tail->next;
cur=next->next;
}
//哨兵卫的next才是有效数据,这里进行保存,为接下来的释放做准备,以免找不到哨兵卫的next
struct Node*phead=newhead->next;
//释放
free(newhead);
return phead;
}
总结:多画图,理解题意即为制胜秘籍。