💛 前情提要💛

本章节是数据结构的链表的相关题目讲解~

以下的内容一定会让你对链表相关知识的题目,有一个颠覆性的认识哦！！！

【以下内容以C语言的方式实现】

以下内容干货满满，跟上步伐吧~

🎓 作者： 热爱编程不起眼的小人物🐐
🔎作者的Gitee：代码仓库
📌系列文章&专栏推荐： 《刷题特辑》、 《C语言学习专栏》、《数据结构_初阶》

📒我和大家一样都是初次踏入这个美妙的“元”宇宙🌏 希望在输出知识的同时，也能与大家共同进步、无限进步🌟

📌导航小助手📌

• 👉前情提要
• 📒面试真题【全面深度解析】
• • 🏷️环形链表【难度：简单】
  • 🏷️ 复制带随机指针的链表【难度：中等】
• 🌟总结

👉前情提要

• 本次题目涉及面试题解答思路&中等难度题目

• 欢迎大家上手测试一波🥰

📒面试真题【全面深度解析】

🏷️环形链表【难度：简单】

🔍题目传送门：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false

• 示例 1：

输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点

• 示例 2：

输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点

• 示例 3：

输入：head = [1], pos = -1输出：false解释：链表中没有环

💡解题关键： 本题目实质询问了两个问题

• 1️⃣判断链表是否为循环链表：

1. 链表的最后一个结点的next指向第一个结点，形成循环链表

2. 链表的最后一个结点的next指向前面的任意一个结点，形成循环链表

3. 链表的最后一个结点的next指向自己的结点，形成循环链表

• 2️⃣如果为循环链表，则循环的入口点是哪个位置

🔥解题思路：「快慢指针」的思想解决相遇问题

• 快慢指针前进的方向相同，且它们步伐的差是恒定的【即快指针的速度是慢指针的两倍】

• 如果链表是存在环的话，「快指针」一定先进入环并一直在环内移动，当「慢指针」刚进入环时，由于「快指针」走得快，每次两指针距离就减少1,最终一定会在某一个结点处追上「慢指针」与之相遇，即套了「慢指针」若干圈

  • 1️⃣快指针：一次走两步

  • 2️⃣慢指针：一次走一步

✊动图示例：

❗特别注意： 可能有同学就疑惑于为什么「快慢指针」的⌈快指针⌋不能一次走3步?走4步?走n步?

• 因为这里就涉及了一个逻辑问题[这也是一个面试真题]

1️⃣证明: ⌈快指针⌋ ⌈慢指针⌋ 一定会在环内相遇,而不是永远追不上

2️⃣证明: ⌈慢指针⌋走一步,⌈快指针⌋走两步? 走三步? 走x步? 行不行

1. 无论⌈快指针⌋走x步,快慢指针之间每次减少的距离不是奇数就是偶数,所以大致的效果都可以类比出来

2. 所以关键在于⌈慢指针⌋进环时与⌈快指针⌋相差的距离N:

   1. 当N为偶数,且每次减少的距离为偶数的时候,就一定能追上

   2. 当N为奇数,且每次减少的距离为奇数的时候,就一定能追上

   3. 当N为偶数，且每次减少的距离为奇数的时候，此时就需要看下一圈环的长度-1的距离[即此时N = 环的长度-1]:

      1. 当 环的长度-1 为偶数，即 重复循环了这种情况，永远不可能相遇

      2. 当环的长度-1为奇数，又因为每次减少的距离为奇数，所以可以追得上

   4. 当N为奇数，且每次减少的距离为偶数的时候，此时就需要看下一圈环的长度-1的距离[即此时N = 环的长度-1]:

      1. 当环的长度-1为偶数, 又因为每次减少的距离为偶数，所以可以追得上

      2. 当 环的长度-1 为奇数，即 重复循环了这种情况，永远不可能相遇

➡️综上： 有两种情况永远不可能相遇

• 1️⃣当⌈慢指针⌋进环时，若快慢指针的差距N为偶数，每次差距减少奇数，且环的长度-1为偶数

• 2️⃣当⌈慢指针⌋进环时，若快慢指针的差距N为奇数，每次差距减少偶数，且环的长度-1为奇数

✨当解决相遇的问题，我们再来看看⌈如何找到循环的入口点⌋

• 此时就可以推导出一个公式满足：一个从相遇点开始走，一个从链表的头部开始走，直至相遇，就是循环入口点的位置

👉实现：

bool hasCycle(struct ListNode *head) {    struct ListNode* slow = head;struct ListNode* fast = head;//相遇 -- 且找到 相遇点while (fast && fast->next){//如果不带环//fast走得快，一定会先结束slow = slow->next; //一次走一步fast = fast->next->next; //一次走两步if (slow == fast){//相遇struct ListNode* meet = fast;//通过推论证明，一个指针从 head 走，//一个指着从 相遇点走//它们就可以在入口点处 相遇     while (meet != head){meet = meet->next;head = head->next;}return meet;  //返回相遇的结点}}return false;}

🏷️ 复制带随机指针的链表【难度：中等】

🔍题目传送门：

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]]

💡解题关键：

• 这题只要想得到思路，解出来就很简单了~

❗本题难点： 拷贝结点好处理，但拷贝带随机指针的结点难处理

• 1️⃣拷贝以后，新链表需要确定每个random则需要去原来的链表一个个去查找，则每个新链表的random处理起来就是O(N*N),效率低

• 2️⃣而且当原链表中存在多个结点的值相同的话，则要找random指向这多个相同中的其中一个结点的话，实则是很难找的，因为拷贝random时确认不了是多个相同中的哪一个

➡️所以我们针对这个模型，进行一点点的改造：

• 将原链表中的每个结点都拷贝一个并链接插入到原结点的后面

• 那我们再处理拷贝链表的时候，拷贝后的链表的random就可以通过第一步链接在原链表中的对应原结点的random指向的结点后面的拷贝结点直接指向，找到拷贝链表的random的指向

copy->random = cur->random->next;以此类推~

❗特别注意：

• 当原结点的random指向的是NULL的时候，就不再需要再访问random->next，而是直接将NULL给copy->random

• 上述步骤执行完后，可以将拷贝原结点的结点拿下来，并链接再一起形成新的链表
  

👉实现：

struct Node* copyRandomList(struct Node* head) {if (head == NULL){return NULL; }//1.拷贝结点 挂在原节点的后面 ，建立对应关系struct Node* cur = head;while (cur){struct Node* next = cur->next;struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;cur->next = copy;copy->next = next;cur = next;}//2.处理copy结点的randomcur = head;while (cur) //将每个结点都处理完{struct Node* copy = cur->next;if (cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;  }//3.拷贝结点取下来，链接到一起，恢复原链表//取下来为尾插：尾插的简单写法就是带一个哨兵位的头结点cur = head;struct Node* copyHead, *copyTail;copyHead = copyTail = (struct Node*)malloc(sizeof(struct Node));while (cur != NULL){struct Node* copy = cur->next;struct Node* next = copy->next;//尾插[带哨兵位的就可以直接 tail后面一直尾插]copyTail->next = copy;copyTail = copyTail->next;//恢复原链表cur->next = next;//继续迭代cur = next;} struct Node* guard = copyHead;copyHead = copyHead->next;free(guard); //释放头结点return copyHead;}

🌟总结

综上，我们基本了解了数据结构中的 “链表重要面试真题” 🍭 的知识啦~~

恭喜你的内功又双叒叕得到了提高！！！

感谢你们的阅读😆

后续还会继续更新💓，欢迎持续关注📌哟~

💫如果有错误❌，欢迎指正呀💫

✨如果觉得收获满满，可以点点赞👍支持一下哟~✨