🍇前言
本章的链表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练习在此就结束了，大家要好好练习噢~
感谢阅读本小白的博客，错误的地方请严厉指出噢~
