·人的才华就如海绵的水，没有外力的挤压，它是绝对流不出来的。流出来后，海绵才能吸收新的源泉。💓💓💓
目录
说在前面
题目一：环形链表
题目二：环形链表 II
题目三：随机链表的复制
SUMUP结尾
说在前面
dear朋友们大家好！💖💖💖我们又见面了，接着上一个篇目，我们接着继续练习有关链表的面试题、OJ题，希望大家和我一起学习，共同进步~
👇👇👇
友友们！🎉🎉🎉点击这里进入力扣leetcode学习🎉🎉🎉
以下是leetcode题库界面：
👇👇👇
🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
以下是NowCoder题库界面：
题目一：环形链表
题目链接：141. 环形链表 - 力扣（LeetCode）
题目描述：
题目分析：
思路：快慢指针法。创建快慢指针fast、slow，快指针每次走两步，慢指针每次走一步，如果fast追击上slow（即fast最终等于slow），则链表带环，否则不带环。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* slow = head, *fast = head;//创建快慢指针fast、slow
while(fast && fast->next)//fast走两步，slow走一步
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)//fast追击上slow，则链表带环
return true;
}
return false;
}思考下列问题：
当然，虽然这道题比较简单，但是有些问题我们还是需要搞清楚：
1、为什么一定会相遇，有没有可能会错过，永远追不上？请证明。
答：不会错过。
证明：
假设slow进环时，fast和slow之间的距离为d，那么在fast追击slow的过程中，距离变化为d、d-1、d-2、d-3、...、2、1、0，最终会减到0。当距离为0时，fast追上slow，也就是每追击一次距离d减小1，所以一定能追上。
2、slow一次走1步，fast走3步可以吗？4步、5步、n步呢？请证明。
答：不稳定，有可能很久都追不上。
证明：
我们先考虑slow走1步，fast走3步的情况，剩下的都是如法炮制。同样假设fast和slow之间的距离为d，那么在fast追击slow的过程中，距离变化为d、d-2、d-4、d-6、...，此时就需要讨论d的奇偶性。如果d是偶数，那么d可以减到0，即fast最终会追上slow，但是如果d是奇数，那么d不是2的倍数，它会错过slow并新的距离为C-1（假设C是环的节点数），进入新一轮的追击过程，直到他们两的距离是2的倍数，此时这一轮就可以追上了。
永远追不上的条件：同时存在C是偶数且距离d（或N）为奇数，那么就会永远追不上。
那是否真的会有这种情况呢？我们需要寻找C和N之间的关系：
证明：
假设slow进环时，fast和slow的距离是N，带环部分的节点数为C，链表不带环部分的节点数为L，slow进环时fast已经在环中转了x圈，则有：
slow走的距离是：L
fast走的距离是：L + xC + (C - N)
由于fast走的距离是slow的三倍，则有：3L = L + xC + C - N
化简得到：2L = (x + 1)C - N
显然C为偶数且N为奇数不能同时成立，也就是说，fast最终总是会追击上slow。
题目二：环形链表 II
题目链接：142. 环形链表 II - 力扣（LeetCode）
题目描述：
题目分析：
思路1：快慢指针法。用题目一中的方法找到fast追击上slow的节点，记为meet，再将head记为cur，让meet和cur同时走，它们会再第一个相交节点相遇，即入环的第一个节点。
那为什么会在第一个相交节点相遇呢？
解：
假设fast追上slow时的节点，即meet节点，逆时针距离入环的第一个节点的距离为N，不带环部分节点数为L，带环部分节点数为C，则有：
slow走的距离是：L + N（fast一次走2步，在一圈内一定能追上）
fast走的距离是：L + xC + N
又因为fast走的距离是slow的两倍，则有：2(L + N) = L + xC + N
化简得到：L = xC- N
显然随着x的变化，指针fast在环内距离入环的第一个节点的距离f(x)是一个周期函数，周期为T = 1，那么L(x)也是关于x的周期函数，周期T = 1。
所以：L = C - N（就比如sinπ、sin3π和sin5π都是相等的）
由此得到不带环部分的节点数等于meet距离入环的第一个节点的节点数相等，所以它们以相同速度移动，一定会再第一个相交节点相遇。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
ListNode* slow = head, * fast = head;//创建快慢指针
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)//fast追上slow
{
ListNode* meet = slow;
ListNode* cur = head;
while (meet != cur)//meet和cur相遇，则为第一个相交节点
{
meet = meet->next;
cur = cur->next;
}
return meet;
}
}
return NULL;//没有相交节点则返回NULL
}思路2：先用思路1的方法找到meet，然后将meet->next设置为newhead，然后让环断裂，使其转化为相交链表找第一个相交节点（上个篇目解析过这类题）。
这个思路可能更好想，但是代码却要更加复杂一些。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
//相交单链表寻找第一个相交节点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
ListNode* cur1 = headA, * cur2 = headB;
int lenA = 0;
int lenB = 0;
while (cur1->next)//统计链表A的长度
{
lenA++;
cur1 = cur1->next;
}
while (cur2->next)//统计链表B的长度
{
lenB++;
cur2 = cur2->next;
}
if (cur1 != cur2)//判断是否有交点
return NULL;
//假设法，设置长短链表
ListNode* LongList = headA, * ShortList = headB;
if (lenA < lenB)
{
LongList = headB;
ShortList = headA;
}
int gap = abs(lenA - lenB);//两链表节点差值
while (gap--)//让长的先走差值的步数
{
LongList = LongList->next;
}
while (LongList != ShortList)//让两链表一起走，第一个相等的就是交点
{
LongList = LongList->next;
ShortList = ShortList->next;
}
return LongList;
}
//带环链表寻找第一个相交节点
struct ListNode *detectCycle(struct ListNode *head) {
ListNode *slow = head, *fast = head;//创建快慢指针
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
ListNode* meet = slow;
ListNode* newhead = meet->next;//新单链表的头
meet->next = NULL;//尾部置为NULL
ListNode* cur = getIntersectionNode(newhead, head);
return cur;
}
}
return NULL;
}第一个函数我们在上一篇目中有详细解析，这里直接CV就可以了。 虽然能够通过，但是修改了链表，本质上不符合题目要求了，但是也是个值得思考的思路。
题目三：随机链表的复制
题目链接：138. 随机链表的复制 - 力扣（LeetCode）
题目描述：
注：深拷贝：拷贝一个值个指向和当前链表一模一样的链表。
题目分析：
思路：快先将新的节点交错插入到原随机链表中，然后完成设置random后再将新的节点尾插到新链表newhead中。
这道题目创建节点其实不难，难就难在random是随机的，应该如何处理random的指向是这道题目的难点。我们如果错位插入，就可以得到新节点和旧链表之间的关系，那么新的节点的random指针都会指向插入了新节点的链表的random的next指针（空指针除外）。
比如，上面原来的第二个节点的random指向了第一个节点，那么新的第二个节点的random就指向第一个节点的next节点。
代码如下：
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
Node* cur = head;
while (cur)//创建新节点并错位插入旧节点
{
Node* copy = (Node*)malloc(sizeof(Node));
copy->val = cur->val;
copy->next = cur->next;
cur->next = copy;
cur = copy->next;
}
cur = head;
while (cur)//设置random指针的指向
{
Node* copy = cur->next;
if (!cur->random)
copy->random = NULL;
else
{
copy->random = cur->random->next;
}
cur = copy->next;
}
cur = head;
//创建新链表
Node* newhead = (Node*)malloc(sizeof(Node));
Node* newtail = newhead;
while (cur)//将新节点尾插到新链表
{
Node* copy = cur->next;
newtail->next = copy;
newtail = newtail->next;
cur->next = copy->next;//恢复原链表
cur = copy->next;
}
if (newtail)
newtail->next = NULL;
return newhead->next;
}这道题目不论是思路还是代码书写都很有难度，如果你看了我的讲解能够独立地写出上面代码（不一定非要和我一样），那么恭喜你，在当前阶段你的链表已经过关了！
SUMUP结尾
数据结构就像数学题，需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题，希望大家一起学习，共同进步~
如果大家觉得有帮助，麻烦大家点点赞，如果有错误的地方也欢迎大家指出~
