【数据结构】一题带你出师链表!

题目链接

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.随机链表的复制题目详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

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