c语言数据结构单链表中随机链表的复制

c语言数据结构单链表中随机链表的复制

文章目录

• c语言数据结构单链表中随机链表的复制
• • 1.随机链表的复制问题
  • 2.解决思路
  • 3.代码的实现

1.随机链表的复制问题

给你一个长度为 n n n的链表，每个节点包含一个额外增加的随机指针 r a n d o m random random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n n n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 n e x t next next 指针和 r a n d o m random random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X X X 和 Y Y Y 两个节点，其中 X . r a n d o m − − > Y X.random --> Y X.random−−>Y 。那么在复制链表中对应的两个节点 x x x 和 y y y ，同样有 x . r a n d o m − − > y x.random --> y x.random−−>y 。

返回复制链表的头节点。

用一个由 n n n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [ v a l , r a n d o m i n d e x ] [val, random_index] [val,randomi​ndex] 表示：
v a l ： val： val：一个表示 N o d e . v a l Node.val Node.val 的整数。
r a n d o m i n d e x ： random_index： randomi​ndex：随机指针指向的节点索引（范围从 0 0 0 到 n − 1 n-1 n−1）；如果不指向任何节点，则为 n u l l null null 。
你的代码 只 接受原链表的头节点 h e a d head head 作为传入参数。
示例 1：

输入： h e a d = [ [ 7 , n u l l ] , [ 13 , 0 ] , [ 11 , 4 ] , [ 10 , 2 ] , [ 1 , 0 ] ] head = [[7,null],[13,0],[11,4],[10,2],[1,0]] head=[[7,null],[13,0],[11,4],[10,2],[1,0]]
输出： [ [ 7 , n u l l ] , [ 13 , 0 ] , [ 11 , 4 ] , [ 10 , 2 ] , [ 1 , 0 ] ] [[7,null],[13,0],[11,4],[10,2],[1,0]] [[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入： h e a d = [ [ 1 , 1 ] , [ 2 , 1 ] ] head = [[1,1],[2,1]] head=[[1,1],[2,1]]
输出： [ [ 1 , 1 ] , [ 2 , 1 ] ] [[1,1],[2,1]] [[1,1],[2,1]]

示例 3：

输入： h e a d = [ [ 3 , n u l l ] , [ 3 , 0 ] , [ 3 , n u l l ] ] head = [[3,null],[3,0],[3,null]] head=[[3,null],[3,0],[3,null]]
输出： [ [ 3 , n u l l ] , [ 3 , 0 ] , [ 3 , n u l l ] ] [[3,null],[3,0],[3,null]] [[3,null],[3,0],[3,null]]

提示：

• 0 < = n < = 1000 0 <= n <= 1000 0<=n<=1000
• − 104 < = N o d e . v a l < = 104 -104 <= Node.val <= 104 −104<=Node.val<=104
• N o d e . r a n d o m Node.random Node.random 为 n u l l null null 或指向链表中的节点

2.解决思路

2.1 复制节点，插入到原节点和下一个节点之间。

   我们通过遍历，在原节点和下一个节点之间插入复制节点。（在这里我把 c u r cur cur看作被复制的节点， c o p y copy copy看作复制后的节点）
   这样做的好处是： c o p y copy copy的 r a n d o m random random就很好表示，他就是 c u r . r a n d o m . n e x t cur.random.next cur.random.next。
2.2 根据原节点 r a n d o m random random，处理复制节点的 r a n d o m random random。

  由于 c o p y copy copy的 r a n d o m random random很好表示，我们就可以通过遍历，一一的把 c o p y copy copy的 r a n d o m random random节点连起来。
2.3 把复制节点解下来链接成一个新链表，恢复原链表链接关系。

  通过以上的步骤我们就可以通过把复制节点解下来链接成一个新链表，恢复原链表链接关系。以此来完成复制随机链表的目标。

3.代码的实现

// 随机链表的拷贝
struct Node {
	int val;
	struct Node* next;
	struct Node* random;
	
};

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
	while (cur)
	{
		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
		copy->val = cur->val;
		// 插入·copy节点
		copy->next = cur->next;
		cur->next = copy;
		cur = copy->next;
	}
	//  根据原节点，处理copy节点的random
	cur = head;
	while (cur)
	{
		struct Node* copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}
		cur = copy->next;
	}
	// 恢复链表
	struct Node* copyHead = NULL; 
	struct Node* copyTail = NULL;
	cur = head;
	while (cur)
	{
		struct Node* copy = cur->next;
		struct Node* next = copy->next;
		if (copyTail == NULL)
		{
			copyTail = copyHead = copy;
		}
		else
		{
			copyTail->next = copy;
			copyTail = copy;
		}
		cur->next = next;
		cur = next;
	}
	return copyHead;
}

   通过以上代码我们就可以实现用c语言复制随机链表了。

最后,这是我在学习c语言数据结构单链表中随机链表复制时的笔记，我觉得想出这个方法的人真的很厉害，我作为一个初学者现在能做到就是站在巨人的肩膀上，不断提高自己。有不对的地方希望大家能够指出，大家一起加油！