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

作者：Dream-Y.ocean

2022 年 9 月 27 日
广东
本文字数：3359 字
阅读完需：约 11 分钟

前情提要

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

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

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

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

👉前情提要

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

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

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

:mag:题目传送门：

给你一个链表的头节点 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️⃣判断链表是否为循环链表：

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

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

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

快慢指针前进的方向相同，且它们步伐的差是恒定的【即快指针的速度是慢指针的两倍】
如果链表是存在环的话，「快指针」一定先进入环并一直在环内移动，当「慢指针」刚进入环时，由于「快指针」走得快，每次两指针距离就减少 1,最终一定会在某一个结点处追上「慢指针」与之相遇，即套了「慢指针」若干圈
1️⃣快指针：一次走两步
2️⃣慢指针：一次走一步

✊动图示例：

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

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

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

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

无论⌈快指针⌋走 x 步,快慢指针之间每次减少的距离不是奇数就是偶数,所以大致的效果都可以类比出来
所以关键在于⌈慢指针⌋进环时与⌈快指针⌋相差的距离N:
当N为偶数,且每次减少的距离为偶数的时候,就一定能追上
当N为奇数,且每次减少的距离为奇数的时候,就一定能追上
当N为偶数，且每次减少的距离为奇数的时候，此时就需要看下一圈环的长度-1的距离[即此时N = 环的长度-1]:
==当环的长度-1 为偶数，即重复循环了这种情况，永远不可能相遇==
当环的长度-1为奇数，又因为每次减少的距离为奇数，所以可以追得上
当N为奇数，且每次减少的距离为偶数的时候，此时就需要看下一圈环的长度-1的距离[即此时N = 环的长度-1]:
当环的长度-1为偶数, 又因为每次减少的距离为偶数，所以可以追得上
==当环的长度-1 为奇数，即重复循环了这种情况，永远不可能相遇==

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

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

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

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

👉实现：

<font color="red"><code class="language-c">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;}</code></font>

复制代码

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

:mag:题目传送门：

示例 1：

<font color="red"><code class="language-c">输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]</code></font>

复制代码

示例 2：

<font color="red"><code class="language-c">输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]</code></font>

复制代码

示例 3：

<font color="red"><code class="language-c">输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]]</code></font>

复制代码

💡解题关键：

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

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

1️⃣拷贝以后，新链表需要确定每个random则需要去原来的链表一个个去查找，则每个新链表的random处理起来就是O(N*N),效率低
2️⃣而且当原链表中存在多个结点的值相同的话，则要找random指向这多个相同中的其中一个结点的话，实则是很难找的，因为拷贝random时确认不了是多个相同中的哪一个

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

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

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

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

❗特别注意：

当原结点的random指向的是NULL的时候，就不再需要再访问random->next，而是直接将NULL给copy->random
上述步骤执行完后，可以将拷贝原结点的结点拿下来，并链接再一起形成新的链表

👉实现：

<font color="red"><code class="language-c">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结点的random    cur = 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;}</code></font>

复制代码

🌟总结

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

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

感谢你们的阅读

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

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/5b4fe610233383a177b8cb8e1】。未经作者许可，禁止转载。

Dream-Y.ocean

关注

还未添加个人签名 2022.06.17 加入

还未添加个人简介

发布

暂无评论

创作场景

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

👉前情提要

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

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

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

🌟总结

Dream-Y.ocean

评论