首页 > 其他分享 >c语言数据结构单链表中随机链表的复制

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

时间:2024-08-04 22:54:15浏览次数:14  
标签:单链 cur random next 链表 表中 copy 节点

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

文章目录

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

标签:单链,cur,random,next,链表,表中,copy,节点
From: https://blog.csdn.net/2401_84272030/article/details/140853577

相关文章

  • 链表part02
    今天是8月3日,学习了链表的第二部分。交换链表两个节点,考察对next的操作和tmp的灵活运用。删除链表的倒数第N个节点,双指针减少遍历次数。链表相交,移动链表尾对齐,其实就是动长链表的指针。环形链表,记住方法。4.24交换链表两个节点题目:给你一个链表,两两交换其中相邻的节点,并......
  • 数据结构:链表经典算法OJ题
    目录前言一、移除链表元素二、反转链表三、合并两个有序链表四、链表的中间节点五、环形链表的约瑟夫问题前言  在了解了链表的相关知识后,我们还需要一些题目进行练习加深对链表这方面知识的理解,也可以用来检测链表这块学的的怎么样,废话不多说,开始上手。一、移......
  • 算法题之旋转链表
    旋转链表给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。示例1:输入:head=[1,2,3,4,5],k=2输出:[4,5,1,2,3]示例2:输入:head=[0,1,2],k=4输出:[2,0,1]提示:链表中节点的数目在范围 [0,500] 内-100<=Node.val<=1000<=k<=......
  • 代码随想录算法训练营day03|203.移除链表元素,707.设计链表,206.反转链表
    203.移除链表元素题目链接:https://leetcode.cn/problems/remove-linked-list-elements/description/我的代码(分头节点和中间节点两种情况操作):/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val......
  • Linux内核-内核链表
    1内核链表内核链表本质就是一个双向循环链表:链表的实现仅用一个include/linux/list.h实现。内核链表有别于传统链表就在节点本身不包含数据域,只包含指针域。故而可以很灵活的拓展数据结构。使用时包含在用户数据结构内部。1.1内核链表结构体structlist_head{struct......
  • leetcode 021:删除链表的倒数第 N 个结点
    LCR021.删除链表的倒数第N个结点给定一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]示例3:输入:head=[1,2],n=1输出:[1]structListNode*removeNthF......
  • C++实现静态链表
    #include<iostream>usingnamespacestd;//定义静态链表的最大容量constintMAX_SIZE=100;//节点类classNode{public:intdata;//节点存储的数据intnext;//节点指向下一个节点的索引(在数组中的位置)//默认构造函数Node():data(0......
  • 链表part01
    今天是8月2日,学习了链表的基础知识。题目主要是链表的基础操作和反转链表,注意虚拟头节点的使用、next的顺序和tmp的灵活使用。1.移除元素题目:给一个链表的头节点head和整数val,请删除链表中所有满足Node.val==val的节点,并返回新的头节点。删除的方法,cur指针挨个遍......
  • 结构体与共用体,链表的学习
    结构体定义        C语言允许用户自己定义一种数据结构,称为结构体。        声明一个结构体类型一般形式为:                strcut 结构体名                {                    成员列表......
  • 141.环形链表
    给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。注意:pos 不作为参数进行传递 。仅仅是为......