【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #

坏幸运 2023-04-19 原文

文章目录

🍇前言

本章的链表OJ练习，是最后的也是最难的。对于本题，我们不仅要学会解题的思路，还要能够通过这个思路正确的写出代码，也就是思路转化为代码的过程，这应该就是最难的地方了吧。
对于OJ练习(5): -> 传送门 <-，环形链表的做法的证明一定要理解透彻，因为面试很可能问到噢。

🍎复制带随机指针的链表

题目链接：-> 传送门 <-。
题目描述：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如：如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点。
也就是复制一个链表。

例如复制下面这个链表：（复制后返回复制后的链表的头节点）

解题思路：

我相信，看到这个题，第一感觉就是暴力把他给复制了。但暴力终会达到O(N^2)，虽然可以过，但如果面试的时候遇到这个问题，面试官可能就会问：如何将时间复杂度降到O(N)呢？
所以这里使用一种O(N)的方法来解这道题。
首先，我们在原链表上的每一个节点后面插入一个与自己有相同值的节点（称为copy节点），然后进行连接，如下：

然后进行的操作是最关键的：再遍历一遍连接了copy节点后的链表，将每一个copy节点的random指向它前一个节点（就是被复制的那个节点，因此这里操作的时候，需要一个指针指向copy节点的前一个节点）的random的next节点，如果copy的前一个节点的random指向NULL，那直接将copy节点的random指向NULL，直到遍历结束，可以得到下面这个链表：

细心观察不难发现，上面的所有copy节点组成的链表实际上就与原链表相同了。
因此最后的操作，就是将每一个copy节点取下来尾插到新的链表上，最后返回这个新链表的头即可。当然啦，这里还需要将原链表复原。
根据上面的思路，会发现，如何将这些过程转换成代码是个难点。这里没得巧，就是多练，多写，正如：无他，唯手熟尔。

⏩下面是代码实现(注意：一边写代码或者看代码，一边要体会整个思路的过程)：

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur = head;
    while (cur)
    {
    	// 创建copy节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        // 存放当前节点的下一个节点的地址，便于连接和继续遍历链表
        struct Node* next = cur->next;
        // 连接
        cur->next = copy;
        copy->next = next;
        cur = next;
    }

    cur = head;
    while (cur)
    {
    	// 同样三个指针遍历
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
		
		// 放置copy的random指针
        if (cur->random == NULL) copy->random = NULL;
        else copy->random = cur->random->next;

        cur = next;
    }
	
	// 新链表的头和连接新链表的指针
    struct Node* copyHead = NULL, *copyTail = NULL;
    cur = head;
    while (cur)
    {
    	// 同样需要三个指针来遍历
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

		// 如果copyHead为NULL，先同时指向头节点
        if (copyHead == NULL) 
        {
            copyHead = copyTail = copy;
        }
        else 
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }

		// 复原原链表
        cur->next = next;
        // 找下一个
        cur = next;
    }

    return copyHead;
}

🍑写在最后

对于单链表的题目练习，最重要的是思路，我们在数据结构阶段要养成画图的习惯，因为它能帮助我们更好的理解。单链表的OJ练习在此就结束了，大家要好好练习噢~

感谢阅读本小白的博客，错误的地方请严厉指出噢~

练习基础 span class token 链表算法数据结构

有关【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #的更多相关文章

区块链之加解密算法&数字证书 - 2
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
postman接口测试工具-基础使用教程 - 2
1.postman介绍Postman一款非常流行的API调试工具。其实，开发人员用的更多。因为测试人员做接口测试会有更多选择，例如Jmeter、soapUI等。不过，对于开发过程中去调试接口，Postman确实足够的简单方便，而且功能强大。2.下载安装官网地址:https://www.postman.com/下载完成后双击安装吧，安装过程极其简单，无需任何操作3.使用教程这里以百度为例,工具使用简单，填写URL地址即可发送请求，在下方查看响应结果和响应状态码常用方法都有支持请求方法:getpostputdeleteGet、Post、Put与Delete的作用get：请求方法一般是用于数据查询，
软件测试基础 - 2
Ⅰ软件测试基础一、软件测试基础理论1、软件测试的必要性所有的产品或者服务上线都需要测试2、测试的发展过程3、什么是软件测试找bug，发现缺陷4、测试的定义使用人工或自动的手段来运行或者测试某个系统的过程。目的在于检测它是否满足规定的需求。弄清预期结果和实际结果的差别。5、测试的目的以最小的人力、物力和时间找出软件中潜在的错误和缺陷6、测试的原则28原则：20%的主要功能要重点测（eg：支付宝的支付功能，其他功能都是次要的）80%的错误存在于20%的代码中7、测试标准8、测试的基本要求功能测试性能测试安全性测试兼容性测试易用性测试外观界面测试可靠性测试二、质量模型衡量一个优秀软件的维度①功能性功
ES基础入门 - 2
ES一、简介1、ElasticStackES技术栈：ElasticSearch：存数据+搜索；QL；Kibana：Web可视化平台，分析。LogStash：日志收集，Log4j:产生日志；log.info(xxx)。。。。使用场景：metrics：指标监控…2、基本概念Index（索引）动词：保存（插入）名词：类似MySQL数据库，给数据Type（类型）已废弃，以前类似MySQL的表现在用索引对数据分类Document（文档）真正要保存的一个JSON数据{name:"tcx"}二、入门实战{"name":"DESKTOP-1TSVGKG","cluster_name":"elasticsear
牛客网专项练习30天Pytnon篇第02天 - 2
1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析：在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1: print(k)k=k/2A.1000 B.10C.11D.9解析：按照题意每次循环K/2，直到K值小于等
ruby - 如何在 ruby 中复制目录结构，不包括某些文件扩展名 - 2
我想编写一个ruby脚本来递归复制目录结构，但排除某些文件类型。因此，给定以下目录结构:folder1folder2file1.txtfile2.txtfile3.csfile4.htmlfolder2folder3file4.dll我想复制这个结构，但不包含.txt和.cs文件。因此，生成的目录结构应如下所示:folder1folder2file4.htmlfolder2folder3file4.dll 最佳答案您可以使用查找模块。这是一个代码片段:require"find"ignored_extensions=[".cs"
ruby 变量作为同一对象(指针？) - 2
>>a=5=>5>>b=a=>5>>b=4=>4>>a=>5如何将“b”设置为实际的“a”，以便在示例中，变量a也将变为4。谢谢。最佳答案 classRefdefinitializeval@val=valendattr_accessor:valdefto_s@val.to_sendenda=Ref.new(4)b=aputsa#=>4putsb#=>4a.val=5putsa#=>5putsb#=>5当您执行b=a时，b指向与a相同的对象(它们具有相同的object_id).当你执行a=some_other_thing时，a将指向
ruby - 在两个 ActiveRecord 类之间合并/复制属性的好方法？ - 2
之前有人问过这个问题，我发现了以下clip关于如何一次设置一个类对象的所有属性，但由于批量分配保护，这在Rails中是不可能的。(例如，您不能Object.attributes={})有没有一种很好的方法可以将一个类的属性合并到另一个类中？object1.attributes=object2.attributes.inject({}){|h,(k,v)|h[k]=vifObjectModel.column_names.include?(k);h}谢谢。最佳答案利用assign_attributes使用:without_prote
Ruby:我怎样才能复制这个数组？ - 2
(跟进我之前的问题，Ruby:howcanIcopyavariablewithoutpointingtothesameobject?)我正在编写一个简单的Ruby程序来在.svg文件中进行一些替换。第一步是从文件中提取信息并将其放入数组中。为了避免每次调用此函数时都从磁盘读取文件，我尝试使用memoize设计模式-在第一次调用后的每次调用中都使用缓存结果。为此，我使用了一个在函数之前定义的全局变量。但是，即使我在返回局部变量之前将该变量.dup为局部变量，调用该变量的函数仍在修改全局变量。这是我的实际代码:#memoizetokeepfromhavingtoreadoriginalfi
【网络】-- 网络基础 - 2
（本文是网络的宏观的概念铺垫）目录计算机网络背景网络发展认识"协议"网络协议初识协议分层OSI七层模型TCP/IP五层(或四层)模型报头以太网碰撞路由器IP地址和MAC地址IP地址与MAC地址总结IP地址MAC地址计算机网络背景网络发展是最开始先有的计算机，计算机后来因为多项技术的水平升高，逐渐的计算机变的小型化、高效化。后来因为计算机其本身的计算能力比较的快速：独立模式：计算机之间相互独立。如：有三个人，每个人做的不同的事物，但是是需要协作的完成。而这三个人所做的事是需要进行协作的，然而刚开始因为每一台计算机之间都是互相独立的。所以前面的人处理完了就需要将数据

【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #

文章目录

🍇前言

🍎复制带随机指针的链表

🍑写在最后

有关【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #的更多相关文章

随机推荐