目录
题目:
本题的解图关键在于画图与看图!
思路分析:
方法一:暴力求解法。
方法二:插入法
方法解析:
步骤一、插入
步骤二、 处理每一个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的指向都是尾节点位置,那么遍历之后,时间复杂度抵达了最高——O(N^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的数值后再进行遍历拆卸的尾插操作。