3. 环形链表 II
链接：142. 环形链表 II
描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例1:
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引
一见到这个题目，你心里一慌，但是你知道这是你最后的机会。所以你疯狂地思考。
你脑子中一时闪过了整个宇宙，又想到了 快慢指针 。
你想着：“既然是要求 链表的入环点，那么我用 环形链表 的方法找到 交点 ，我又双叒叕看过某位帅气的博主(还是我)的上一篇博客，里面有个叫做 相交链表 的问题，那么我把这个 入环的第一个节点 看作是 两个相交链表的尾结点 不就可以了，这就转换成了链表相交的问题了！我真是个天才！”
于是你自信的写下了你的思路。
思路1：
先利用 快慢指针 ，以 环形链表 的解法，找到 fast 和 slow 相交的点。然后将这个 交点 给为 meetnode 。作为两条新链表的尾。那么 meetnode->next 为某条新链表的头。然后 入环点 ，就可以看做是两条链表的交点。
然后就是 相交链表 的做法，我就不多赘述了~
代码：
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast, *slow; fast = slow = head; struct ListNode* tail = NULL; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; // 相遇 if (fast == slow) { tail = slow; break; } } // 没有相遇 if (tail == NULL) { return NULL; } struct ListNode* newHead = tail->next; int lenH = 1, lenN = 1; struct ListNode* curH = head, *curN = newHead; while (curH != tail) { lenH++; curH = curH->next; } while (curN != tail) { lenN++; curN = curN->next; } struct ListNode* longList = lenH > lenN ? head : newHead; struct ListNode* shortList = lenH > lenN ? newHead : head; int gap = abs(lenH - lenN); while (gap--) { longList = longList->next; } while (longList != shortList) { longList = longList->next; shortList = shortList->next; } return longList; }
面试官看了你的做法，点点头，说：“小伙子很不错嘛！知道举一反三！看在你这么聪明的份上，我再教你个厉害的！怎么样？”
你点点头，于是面试官开始了他的讲解。看思路2↓
思路2(精讲)：
面试官拿着笔，在纸上写下了三个大字：“公式法。”
面试官举着笔，不可一世地说：“这个方法的难点在于公式推导的过程，只要推导出了公式，解题就变得十分简单。”
然后眉飞色舞地继续说：“先把结论告诉你吧：一个指针从 相遇点 开始走，一个指针从 链表头 开始走，它们会在 环的入口点 相遇。”
接下来，就让我来为你推导公式：
由于 fast 的速度是 slow 的 2 倍。
所以便可以得出这个式子：2 ( L + x ) = L + N * c + x，而这个式子又可以进行推导：
2 ( L + x ) = L + N * c + x ↓ L + x = N * c ↓ L = N * c - x ↓ L = ( N - 1 ) * c + c - x
其实这里 公式已经推导 完成：L = ( N - 1 ) * c + c - x 。但是这个公式到底是什么意思？
根据这个我们也就可以做出这道题目了。
讲完，面试官得意地笑着说：“怎么样，同学？你学会了吗？”
你说：“学废了学废了，我感觉我的链表水平更上一层楼~” 但是说完你又感觉到了不对劲，面试官又展现出他邪魅的笑容。
面试官说：“那么你很懂咯，你只要再把这道题目写出来，你就通过本次面试！怎么样，你有信心吗？”
你内心略微慌张，但是表面稳如老狗，说到：“来吧！”
“好的，接下来，这道题目叫做：复制带随机指针的链表！”
4. 复制带随机指针的链表
描述：
给你一个长度为 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 作为传入参数。
示例1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random 为 null 或指向链表中的节点。
看到这道题目后，你的第一感觉是，这个链表结构含有 三个成员 ：
struct Node { int val; struct Node* next; // 下一个节点的地址 struct Node* random; // 指向随机节点的指针 };
然后你看到 复制 两字，你和面试官说：“这不是只要复制原链表的每个节点，将其链接起来不就行了？”
面试官听到这句话，优哉游哉地问：“那你的 random 呢？这个你怎么复制？”
你一听，顿时感觉有点心慌。心里想：“对啊，这道题目哪有这么简单。题目里说了它是 深拷贝 ，那么就应该完全复刻啊！并且我即使知道了原链表中和 random 链接的节点，我也不知道 random 和它的相对位置啊！这到底该咋办？”
面试官试着引导你的思路：“不知道你有没有这样的经历，我之前高中上英语课老师要求我们当场写阅读理解时，我虽然有答案。可这答案可不是那么好 copy 的。“
面试官拿起水杯，喝了口水，继续说：“为了不让老师发现，你得在原题目后 偷偷 写上答案。虽然你知道答案，但是你 找不到答案的位置 啊，所以你还得 通过 这份答案，画出答案所在的位置。然后为了防止老师发现你 copy 的痕迹，你得将你 copy 的答案和你划出的答案位置 串联 起来，并且抹除 掉之前的痕迹。你之前有过这样吗？”
你一听，恍然大悟，说到：“哦！我明白了！偷偷写上答案 是我可以在原链表中每个节点的后面，复制这个节点，插入到原节点和下一个节点之间；通过答案画出答案所在的位置 就相当于我知道 复制的节点是在原节点的后面 ，那么如果我已经知道原节点的 random 那么我 复制节点的 random 不就是 原节点的random的next节点？串联答案，抹除痕迹 就是将 复制节点 链接为新链表，和原链表断开链接，恢复原链表！我悟了！”
面试官听了点了点头，说道：“请开始你的表演！友情提示，虽然你的思路差不多对了，但是注意把控细节哦~”
思路(精讲)：
思路其实在上面已经描述的差不多了，所以这里说一下细节。
首先，我们给定一个 copy 节点。在原链表每个节点的后面和这个节点的下一个节点之间插入 copy 节点。
这里就对细节有一定的要求。我们就把遍历原链表的节点叫做 cur 吧。
如果 cur 为空，则不进行拷贝。我们插入的 copy 节点是 动态开辟 的。我们需要将 copy 链接到 cur->next ，然后在让 cur->next 给定为 copy 。随后 cur 就需要原节点的后方，也就是当前 copy 节点的 next 。这就考察了 任意插入元素。
其次，根据原节点 random ，处理 copy 节点的 random 。
其实我们现在已经将 copy 节点和 原链表建立了联系。
原链表的 random 为 cur->random 、而我们插入的 copy 节点也需要链接。如果我们原链表的当前节点的 random 为 cur->random ，那么我的 copy 节点的 random 节点的相对位置应该和当前节点相同。而我们的当前节点的 random 的后方的 拷贝节点 就是这个 copy 节点的 random 。那么我 copy->random 就等于 cur->random->next 。这样不就链接起来了？
这过程中只要处理好迭代关系就可以了，但是需要注意，当 random 指向为 NULL 时，拷贝处也为 NULL。
最后，复制节点链接为新链表，原链表恢复。
完成这一步，我们需要 copyhead 和 copytail 作为复制链表的头和尾。
而复制节点链接为新链表的过程实际上就是 尾插 。所以要注意一下 空链表尾插 和 正常尾插 的情况。
并且在这过程中，将原链表的链接逐渐恢复，这些就需要自己把控了~
代码：
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; // 1. 在原节点后插入复制节点 while (cur) { // 插入复制节点 struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; // cur往后迭代 cur = copy->next; } // 2. 根据原节点的random，处理复制节点的random cur = head; while (cur) { // copy节点在cur的后面 struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = copy->next; } // 3. 复制节点链接为新链表，原节点恢复 struct Node* copyHead = NULL, *copyTail = NULL; cur = head; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next;// 记录原链表的下一个节点 // 复制节点链接为新链表(本质为尾插) if (copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copy; } cur->next = next;// 恢复链接 cur = next; } return copyHead; }
解完这道题目后，你自信地说：“面试官，你看我行吗？”
面试官笑着说：“哈哈哈，小伙子厉害呀！我为你点赞！本次面试你通过了，回去等通知吧！💇♂”
到这里本篇博客就到此结束了。
说真的，博主还是第一次以这种形式写博客，不知道大家的观感如何。希望这篇博客能帮助大家理解这些OJ题，因为 环形链表系列问题 是十分经典的面试题，而普通的讲解我感觉过于生涩，这样可能更容易理解一些，而且偶尔皮一下还是很不错的(doge)。
还是老规矩，大家在看完这些题目后还是亲自去画画图，实践一下。多写多练才能学好数据结构。
这期结束，链表OJ也就到此收官了。之后我会陆续为大家带来博主在学习数据结构时总结的知识点，更多精彩内容，敬请期待~
如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！
我是anduin，一名C语言初学者，我们下期见！
