建立网站的教学书籍,网站排名必做阶段性seo策略,建设银行的英语网站,云南省网站建设文章目录#x1f347;前言#x1f34e;复制带随机指针的链表#x1f351;写在最后#x1f347;前言 本章的链表OJ练习#xff0c;是最后的也是最难的。对于本题#xff0c;我们不仅要学会解题的思路#xff0c;还要能够通过这个思路正确的写出代码#xff0c;也就是思路…
文章目录前言复制带随机指针的链表写在最后前言 本章的链表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练习在此就结束了大家要好好练习噢~ 感谢阅读本小白的博客错误的地方请严厉指出噢~
