导航网站没有内页没有了,怎样做网站的优化排名,高端品牌粉碎机,网站的制作哪家好目录
题目#xff1a;
本题的解图关键在于画图与看图#xff01;
思路分析#xff1a;
方法一#xff1a;暴力求解法。
方法二#xff1a;插入法
方法解析#xff1a; 步骤一、插入
步骤二、 处理每一个copy的randdom指针⭐————重点
步骤三、拆卸节点
代码…目录
题目
本题的解图关键在于画图与看图
思路分析
方法一暴力求解法。
方法二插入法
方法解析 步骤一、插入
步骤二、 处理每一个copy的randdom指针⭐————重点
步骤三、拆卸节点
代码演示 题目
给你一个长度为 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 作为传入参数。 题目大意复制一个单链表并返回一个单链表需要复制的单链表它的节点结构是有一个next指针和一个random指针next指针和普通单链表的next指针一样但是random指针是随机指向链表内部的任意节点或者指向NULL。现在我们要完美的复制一个这样的链表并返回它。 题源138. 随机链表的复制 - 力扣LeetCode 本题的解图关键在于画图与看图 思路分析
对于本题的关键是random指针的复制。
如何将每一个节点的random完完全全的这是我们需要思考的问题为此我们分为两种方法。
方法一暴力求解法。
首先将原链表A 完整的复制下来当然只是复制指针next和指针的数据。
而后设立一个指针copy 专门的对复制下来的链表B 进行遍历。
之后再设置一个指针rand 专门对原链表A进行遍历并且对链表进行计数。
最后开始遍历因为链表A和链表B的元素一样所以我们再使用copy对链表B的random指向的时候可以先使用指针rand寻找相对因节点的rand指针指向的位置并计数然后将计数给指针copy让其进行遍历。
而对于寻找相应节点的rand指针指向的位置是看节点中的数值是否一样。
缺点如果使用了最坏的结果所有random的指向都是尾节点位置那么遍历之后时间复杂度抵达了最高——ON^2
且我们寻找对于节点的random指向是通过节点内的数值元素所以如果元素都一样那就很难分别random要找的是那一个 方法二插入法
我们再原链表的每一个节点后插入一个新的节点通过节点和节点之间的联系完成random的指向复制操作最后将每一个插入的新节点从原链表上拆除并重新组装在一起返回最后的链表。 优点这种方法解决了上面暴力解法的效率问题上面的暴力解法因为拷贝的链表和原链表没有联系所以需要遍历操作。
而这种方法使得拷贝的节点处在了原节点的后面使得拷贝节点的一切数值和指针指针都可以模仿原节点操作也就说数值可以复制而随机指针可以变成源节点的随机指针的next。
方法解析 步骤一、插入
再遍历中进行空间的开辟并且利用遍历形成局部变量方便之后的操作。
copy的next指向cur的next 然后cur的next指向copy 之后cur等于copy的next 这一步创建临时的局部变量copy空间利用遍历将每一次遍历中创建的copy插入再原链表上。 步骤二、 处理每一个copy的randdom指针⭐
将上一步中的cur返回头节点随后设立临时的局部指针copy 指向复制节点。
再对random进行复制之前需要为random指向NULL的节点进行单独处理。
之后将cur-random-next赋值与copy-random
再复制完毕后将cur移动道copy-next的位置也就是原链表的节点位置,而copy直接再一开始的位置设置为cur-next的位置上作为临时变量。 步骤三、拆卸节点
设置一个新的指针next用来恢复原链表和作为临时变量使用
同时定义两个指针作为拆下来组装后的头节点和尾节点newhead和newtail
再将cur指针返回头节点进行遍历和拆卸操作同时设立copy指向复制节点
最后当然需要注意设立的newhead和newtail初始值是NULL所以先要进行赋值赋予copy的数值后再进行遍历拆卸的尾插操作。 代码演示
