【数据结构与算法】2道面试真题，带你领略算法思想【附思路、动图、源码】

💛 前情提要💛

本章节是

数据结构

的

链表

的相关

题目

讲解~

以下的内容一定会让你对

链表

相关知识的题目,有一个颠覆性的认识哦！！！

【以下内容以

C语言

的方式实现】

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

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

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

📌导航小助手📌

👉前情提要

• 本次题目涉及面试题解答思路&中等难度题目
• 欢迎大家上手测试一波🥰

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

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

🔍题目传送门：
Leetcode：141. 环形链表
给你一个链表的头节点

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(structListNode*head){structListNode* slow = head;structListNode* fast = head;//相遇 -- 且找到 相遇点while(fast && fast->next){//如果不带环//fast走得快，一定会先结束

        slow = slow->next;//一次走一步
        fast = fast->next->next;//一次走两步if(slow == fast){//相遇structListNode* meet = fast;//通过推论证明，一个指针从 head 走，//一个指着从 相遇点走//它们就可以在入口点处 相遇while(meet != head){
                meet = meet->next;
                head = head->next;}return meet;//返回相遇的结点}}return false;}

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

🔍题目传送门：
Leetcode：138. 复制带随机指针的链表

示例 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
• 上述步骤执行完后，可以将拷贝原结点的结点拿下来，并链接再一起形成新的链表

👉实现：

structNode*copyRandomList(structNode* head){if(head ==NULL){returnNULL;}//1.拷贝结点 挂在原节点的后面 ，建立对应关系structNode* cur = head;while(cur){structNode* next = cur->next;structNode* copy =(structNode*)malloc(sizeof(structNode));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;

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

🌟总结

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

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

感谢你们的阅读😆

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

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

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