复制带随机指针的链表

前言

题目：

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer

代码实现

struct Node
{
    
	int val;
	struct Node* next;
	struct Node* random;

};
struct Node* copyRandomList(struct Node* head)
{
    

	struct Node* copy = NULL;
	struct Node* cur = head;
	//复制结点
	while (cur)
	{
    
		copy = (struct Node*)malloc(sizeof(struct Node));
		//复制
		copy->val = cur->val;
		copy->next = cur->next;
		cur->next = copy;
		//
		cur = copy->next;
	}

	//给random赋值
	cur = head;
	while (cur)
	{
    
		copy = cur->next;
		if (cur->random == NULL)
		{
    
			copy->random = NULL;
		}
		else
		{
    
			copy->random = cur->random->next;
		}
		cur = cur->next->next;
	}

	//恢复链表，拆分复制的链表
	struct Node* tail = NULL, * newhead = NULL;
	cur = head;
	while (cur)
	{
    
		copy = cur->next;
		if (tail == NULL)
		{
    
			newhead = tail = copy;
		}
		else
		{
    
			tail->next = copy;
			tail = tail->next;
		}
		//恢复链表
		cur->next = copy->next;
		//迭代
		cur = copy->next;
	}
	return newhead;
}

分析

已知存在如下链表，我需要将该链表复制，然后返回复制后的链表的头指针！

First

首先我们看下图

我们先将链表的各个结点进行一个复制，然后将复制后的结点链接到原链表两两数据之间，如图所示，复制7结点之后，将复制后的结点插入到7和13之间即可，因此有如下代码；

struct Node* copy = NULL;
struct Node* cur = head;
//复制结点
while (cur)
{
    
    //创造结点
	copy = (struct Node*)malloc(sizeof(struct Node));
	//复制
	copy->val = cur->val;
	copy->next = cur->next;
	cur->next = copy;
	//重新指向
	cur = copy->next;
}

Next

在将链表复制后插入到原链表之后，我们接下来就需要对复制之后的结点中的random进行一个赋值，如图所示。

cur = head;
while (cur)
{
    
	copy = cur->next;
	if (cur->random == NULL)
	{
    
		copy->random = NULL;
	}
	else
	{
    
		copy->random = cur->random->next;
	}
	cur = cur->next->next;
}

cur是用来便利原链表的一个指针，每次前进两步。将cur的random所指向的next给copy的random即可。

Last

struct Node* tail = NULL, * newhead = NULL;
cur = head;
while (cur)
{
    
	copy = cur->next;
	if (tail == NULL)
	{
    
		newhead = tail = copy;
	}
	else
	{
    
		tail->next = copy;
		tail = tail->next;
	}
	//恢复链表
	cur->next = copy->next;

	//迭代
	cur = copy->next;
}

接下来就要将链表拆下来，然后对原链表进行还原；这个逻辑比较简单，再次不进行赘述！