【数据结构】1道经典面试题带你出师链表!

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

​编辑

题目链接

138. 随机链表的复制 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 作为传入参数。

题目详情

​编辑

解题思路及图解

1. 逐一拷贝链表结点并将其链接在原结点的后面(操作图示如下)​编辑

2. 拷贝结点的random:把原结点后面的拷贝结点的random和原结点random的后一个结点拷贝起来(操作图示如下)​编辑按照这个思路,将所有的拷贝结点的random连接起来:​编辑

3. 将拷贝结点摘下尾插到新链表中,同时恢复原链表(操作图示如下)​编辑逐一将拷贝结点尾插到新链表的同时恢复原链表的链接关系,最后返回newhead即可​编辑

解题代码

综上,该题完整解题代码如下:

struct Node* BuyNode(int x)

{

    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));

    if (newnode == NULL)

    {

        perror("malloc fail::");

        return NULL;

    }

    newnode->val = x;

    newnode->next = NULL;

newnode->random=NULL;

    return newnode;

}




struct Node* copyRandomList(struct Node* head)

{

//1.逐一拷贝链表结点并将其链接在原结点的后面




struct Node*cur=head;

while(cur)

{

int data=cur->val;

struct Node*new=BuyNode(data);

new->next=cur->next;

cur->next=new;

cur=cur->next->next;

}




//2.拷贝结点的random,把原结点后面的拷贝结点的random和原结点random的后一个结点拷贝起来.




cur=head;

while(cur)

{

if(cur->random!=NULL)

{

cur->next->random=cur->random->next;

}

else

{

cur->next->random=cur->random;

}

cur=cur->next->next;

}




//3.将拷贝结点摘下尾插到新链表中,同时恢复原链表.




cur=head;

struct Node*newhead=NULL;

struct Node*tail=newhead;//记录新表尾

while(cur)

{

//先把新结点给新链表

if(newhead==NULL)

{

newhead=cur->next;

tail=newhead;

}

else

{

tail->next=cur->next;

tail=tail->next;

}




//再改变老节点的关系

cur->next=tail->next;

cur=cur->next;

}




if(tail!=NULL)//防止空指针解引用

{

tail->next=NULL;

}




return newhead;




}

提交运行:

​编辑

结语

        这是一道经典的链表面试题目,其中不仅仅是考察我们对题目的思路,同样也需要我们有很扎实的链表插入,删除,链接等操作的基本功.如果可以很轻松的完成这道题,那么恭喜你,你的链表已经达到了可以出师的水平,请继续向着星辰大海进发吧!

        希望这篇对Leetcode:138.随机链表的复制题目详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

        学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

相关文章推荐

【数据结构】 10 道经典面试题目带你玩转链表

【数据结构】线性表的链式存储结构

【数据结构】链表的八种形态

【数据结构】 C 语言实现单链表万字详解 ( 附完整运行代码 )

【数据结构】 C 语言实现带头双向循环链表万字详解 ( 附完整运行代码 )

【数据结构】深入浅出理解链表中二级指针的应用

​编辑

​