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

🍇前言

• 本章的链表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练习在此就结束了，大家要好好练习噢~

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