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

修修修也

发布于 2024-04-01 15:59:08

610

发布于 2024-04-01 15:59:08

文章被收录于专栏：修也的进阶日记修也的进阶日记

题目链接

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 作为传入参数。

题目详情

解题思路及图解

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

拷贝结点的random:把原结点后面的拷贝结点的random和原结点random的后一个结点拷贝起来(操作图示如下)

按照这个思路,将所有的拷贝结点的random连接起来:

将拷贝结点摘下尾插到新链表中,同时恢复原链表(操作图示如下)

逐一将拷贝结点尾插到新链表的同时恢复原链表的链接关系,最后返回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;

}

提交运行: