0
0

【数据结构与算法】8道链表面试真题超详剖析，带你领略算法思想【附思路、动图、源码】

💛 前情提要💛

本章节是

数据结构

的

链表

的相关

基础题目

讲解~

以下的内容一定会让你对

链表

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

❗以下内容以

C语言

的方式实现❗

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

作者介绍：

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

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

📌导航小助手📌

👉前情提要

  • 大家可以跟着本文的题目讲解进行链表相关知识的复习&加深- 若大家对链表还不太熟悉or需要回顾一下基本知识，可点击单链表、带头+双向+循环链表至相关文章进行回顾
  • 也欢迎大家上手测试一波🥰

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

🏷️ 移除链表元素【难度：简单】

🔍题目传送门：
Leetcode：203. 移除链表元素
给你一个链表的头节点 

head

和一个整数 

val

，请你删除链表中所有满足 

Node.val == val

的节点，并返回新的头节点

  • 示例 1：

这里是引用

输入：head =[1,2,6,3,4,5,6], val =6
输出：[1,2,3,4,5]
  • 示例 2：
输入：head =[], val =1
输出：[]
  • 示例 3：
输入：head =[7,7,7,7], val =7
输出：[]

💡解题关键：

  • 我们只需要遍历链表，一一比较结点的val是否为要删除的- 1️⃣若为要删除的结点：先释放掉此结点，再将此结点的上一结点链接到此结点的下一结点- 2️⃣否则，继续遍历比较

❗特别注意：

  • 因为单链表只有后驱指针，无法像带头+双向+循环链表轻易地直接访问某个结点的上一结点
  • 所以遍历的时候需要同时安排前（prev）后（cur）指针，去记录上个结点和当前结点的位置

🔥特殊情况：

  • 1️⃣如果第一个结点就是要删除的结点val：这种情况下我们需要连头指针head 一起改变挪动
  • 2️⃣如果整个链表全是要删除的结点val，则也同样连头指针head一起挪动

✊动图示例：

在这里插入图片描述

👉实现：

structListNode*removeElements(structListNode*head,int val){structListNode* cur = head;structListNode* prev =NULL;//边走边删除 //直至cur走到NULL就停止while(cur){//要删除结点时：if(cur->val == val){structListNode* next = cur->next;//说明要删的是 第一个结点if(prev ==NULL){free(cur);
                head = next;
                cur = next;}else{free(cur);
                prev->next = next;
                cur = next;}}//不需要删除结点时：else{
            prev = cur;
            cur = cur->next;}}return head;}

➡️补充：

  • 这里设计得也很巧妙，用cur来当循环的结束标志，当链表整体为NULL的时候，cur也就为NULL，直接不进入循环，执行return head语句，程序结束

🏷️ 反转链表【难度：简单】

🔍题目传送门：
Leetcode：206. 反转链表
给你单链表的头节点

head

，请你反转链表，并返回反转后的链表

示例 1：

这里是引用

输入：head =[1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

这里是引用

输入：head =[1,2]
输出：[2,1]

示例 3：

输入：head =[]
输出：[]

💡解题关键：

  • 本质：将箭头反转

➡️思路一： 三指针循环反转【n1、n2、n3】

  • 1️⃣n1指针负责不断往后遍历链表，与n2指针一起进行反转箭头【箭头指向n1】
  • 2️⃣n3指针负责迭代【作导向的作用】

✊动图示例：

在这里插入图片描述

❗特别注意：

  • n3指针在往后作为导向迭代最后一步的时候，需要判断n3此时是否为NULL,否则将会造成n3 = n3->next对空指针访问next的错误
  • 此方法为在原链表基础上反转

🔥特殊情况：

  • 如果链表为NULL或者只有一个元素的时候，就不需要反转了

👉实现：

structListNode*reverseList(structListNode* head){if(head ==NULL|| head->next ==NULL){return head;}structListNode* n1 =NULL;structListNode* n2 = head;structListNode* n3 = head->next;while(n2){
        翻转
        n2->next = n1;

        迭代 -- 循环一致往后走
        n1 = n2;
        n2 = n3;//最后一步的时候：n3有可能为NULL//所以需要提前判断if(n3){
            n3 = n3->next;}}return n1;}

➡️思路二： 头插反转（迭代版）

  • 1️⃣即新建一个头newhead，让其指向NULL
  • 2️⃣然后不断从原链表中取结点去头插（指向）newhead，即可达反转的效果

✊动图示例：

在这里插入图片描述

❗特别注意：

  • 此方法为取结点下来头插，不在原链表上反转

👉实现：

structListNode*reverseList(structListNode* head){structListNode* cur = head;structListNode* newhead =NULL;while(cur){//即不断取结点下来，头插到NULL前面去structListNode* next = cur->next;
        
        cur->next = newhead;

        newhead = cur;

        cur = next;}return newhead;}

❗补充：

  • 这个思路也适用于一个结点和NULL链表的情况

🏷️ 链表的中间结点【难度：简单】

🔍题目传送门：
Leetcode：876. 链表的中间结点
给定一个头结点为

head

的非空单链表，返回链表的中间结点

如果有两个中间结点，则返回第二个中间结点

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3(序列化形式：[3,4,5])

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4(序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点

💡解题关键：

  • 利用快慢指针遍历链表，停下来的时候，慢指针所指向的结点就是中间结点

🔥快慢指针的思想：

  • 本质：为了解决“先让一个指针遍历一次链表得出链表的长度，继而再遍历一次去中间位置”的连词循环问题，提出了快慢指针的一次循环即可解决问题的办法
  • 快慢指针前进的方向相同，且它们步伐的差是恒定的【即快指针的速度是慢指针的两倍】
  • 所以当快指针走到最后一个结点的时候，慢指针刚好到中间结点- 1️⃣快指针：一次走两步- 2️⃣慢指针：一次走一步

✊动图示例：

在这里插入图片描述

👉实现：

structListNode*middleNode(structListNode* head){structListNode* fast = head;structListNode* slow = head;while(fast !=NULL&& fast->next !=NULL){
        slow = slow->next;
        fast = fast->next->next;}return slow;}

🏷️ 链表中倒数第k个结点【难度：简单】

🔍题目传送门：
剑指 Offer 22. 链表中倒数第K个结点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 

6

个节点，从头节点开始，它们的值依次是

 1、2、3、4、5、6

。这个链表的倒数第 

3

个节点是值为 

4

的节点。

示例 1：

给定一个链表:1->2->3->4->5, 和 k =2.

返回链表 4->5.

💡解题关键：

  • 同样利用与上题思想相同的快慢指针

➡️思路： 快慢指针

返回倒数第

K

个结点，即返回正数第

总长度-K

个结点

❓那我们在不知道总长度的情况如何下，如何走

总长度-K

步呢

  • 1️⃣那我们便可以先让fast指针走K步，那此时fast指针离最后一个结点的距离就是总长度-K
  • 2️⃣我们再让slow指针在第一个结点位置出发，fast走一步，slow走一步，同时前进，都走了总长度-K步
  • 3️⃣这样，当fast走到空的时候，slow指针指向的就是正数第总长度-K个结点，即倒数第K个结点

❗综上：

  • 相当于让fast指针作一个计数器，先走K步，作slow指针的导向，指引其走总长度-K步，找到倒数第K个结点

✊动图示例：

在这里插入图片描述

🔥特殊情况：

  • 当fast走K步的时候，如果K步还没走完fast就为NULL，证明倒数第K个结点不在链表长度范围之内或者为NULL链表，直接结束程序

👉实现：

structListNode*getKthFromEnd(structListNode* head,int k){structListNode* fast = head;structListNode* slow = head;//fast先走k步while(k--){//如果k还没走完，fast就为NULL了if(fast ==NULL){//说明K比链表长度都要长//也说明 链表可能为空returnNULL;}

        fast = fast->next;}//再同时走//fast为NULL的时候结束while(fast){
        slow = slow->next;
        fast = fast->next;}return slow;}

🏷️ 合并两个有序链表【难度：简单】

🔍题目传送门：
Leetcode：21. 合并两个有序链表
将两个升序链表合并为一个新的 

升序

链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

示例 1：

这里是引用

输入：l1 =[1,2,4], l2 =[1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 =[], l2 =[]
输出：[]

示例 3：

输入：l1 =[], l2 =[0]
输出：[0]

💡解题关键：

  • 两个链表的结点一一比较，一开始取较小的结点作为新链表的头，然后取较小的结点尾插到新链表上

➡️思路： 三指针遍历

  • 1️⃣先比较两个链表的第一个结点，取较小的作为新链表的头
  • 2️⃣一一比较取较小的结点尾插到新链表上，然后往后走继续比较
  • 3️⃣当某一链表已遍历完，而另外一链表没遍历完的时候，直接将其剩下的尾插到新链表上

❗特别注意：

  • 链表的合并并不像数组合并一样，需要新开一个数组，而链表是可以直接相互链接，继而达到合并的效果

✊动图示例：

在这里插入图片描述

🔥特别情况：

  • 需要判断L1与L2各自的链表是否为NULL，如果有一个链表为NULL，就无需合并，可以直接返回另外一个链表

👉实现：

structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){structListNode* l1 = list1;structListNode* l2 = list2;if(l1 ==NULL){return l2;}if(l2 ==NULL){return l1;}structListNode* head =NULL;structListNode* tail =NULL;if(l1->val < l2->val)//但是，如果这里任意一个是 NULL的话，就崩了 ; 所以上面得加上 判断{//先直接判定谁的第一个元素 作为 新链表的头//先取一个小的 去作 头
        head = tail = l1;
        l1 = l1->next;}else{
        head = tail = l2;
        l2 = l2->next;}while(l1 && l2)//两个都没结束，就继续{//取小的尾插到新链表if(l1->val < l2->val){
            tail->next = l1;
            l1 = l1->next;
            tail = tail->next;}else{
            tail->next = l2;
            l2 = l2->next;
            tail = tail->next;}}//结束了，如果有一方还部位NULL，则把其剩下的全链 到 新链表上if(l1){
        tail->next = l1;}else{
        tail->next = l2;}return head;}

🏷️ 分割链表【难度：简单】

🔍题目传送门：
Leetcode：面试题 02.04 分割链表
给你一个链表的头节点 

head

和一个特定值 

x

，请你对链表进行分隔，使得所有 小于

x

的节点都出现在 大于或等于

x

的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置

示例 1：

这里是引用

输入：head =[1,4,3,2,5,2], x =3
输出：[1,2,2,4,3,5]

示例 2：

输入：head =[2,1], x =2
输出：[1,2]

💡解题关键：

  • 将结点一一比较特定值，将小于的拿出来放在一个新链表中，将大于等于的也同样操作，最后再链接在一起

➡️思路：

  • 1️⃣把小于X的尾插到一个新链表中
  • 2️⃣把大于X的尾插到另外一个新链表中
  • 3️⃣最后将两个链表链接到一起

✊动图示例：

  • 第一步：分出大于等于特定值的数，和小的数在这里插入图片描述
  • 第二步：将两个链表链接在一起在这里插入图片描述

❗特别注意：

  • 最后一定要将greaterTail->next置为NULL,否则有可能就会造成闭环的情况
  • 因为在原本的链表里，greaterTail最后所指的结点不一定为最后一个结点
  • 若不是最后一个结点，则greaterTail->next就指向原链表中的下一个结点（不为NULL），则在链接后的新链表中就指向了前面的某个结点，形成闭环，无法结束

👉实现：

structListNode*partition(structListNode* head,int x){structListNode* lessHead =NULL;structListNode* lessTail =NULL;structListNode* greaterHead =NULL;structListNode* greaterTail =NULL;
    
    lessHead = lessTail =(structListNode*)malloc(sizeof(structListNode));
    greaterHead = greaterTail =(structListNode*)malloc(sizeof(structListNode));

    lessTail->next =NULL;
    greaterTail->next =NULL;structListNode* cur = head;while(cur){if(cur->val < x){
            lessTail->next = cur;
            lessTail = lessTail->next;
            cur = cur->next;}else{
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
            cur = cur->next;}}//链接两个链表
    lessTail->next = greaterHead->next;//置空，否则会造成成环的情况
    greaterTail->next =NULL;

    head = lessHead->next;free(greaterHead);free(lessHead);return head;}

🏷️ 回文链表【难度：简单】

🔍题目传送门：
Leetcode：234. 回文链表
给你一个单链表的头节点 

head

，请你判断该链表是否为回文链表

  • 如果是，返回 true
  • 否则，返回 false

示例 1：

这里是引用

输入：head =[1,2,2,1]
输出：true

示例 2：

这里是引用

输入：head =[1,2]
输出：false

➡️思路一： 放置数组比较

  • 1️⃣开一个数组，并将链表的所以结点的val放进数组里
  • 2️⃣而后一头一尾两个指针相互比较，靠近，看是否每个值都相同

❗特别注意：

  • 这种方法的空间复杂度为O(N)，不符合O(1)，还需要优化

➡️思路二： 逆置比较

  • 1️⃣先找到链表中的中间结点【利用快慢指针】
  • 2️⃣从中间结点开始的后半部分链表逆置（反转）【利用反转链表】
  • 3️⃣此时虽然没有正真地断开链表，但我们可以将中间结点后半部分逆置的链表看作新的链表，继而比较此链表与前半部分的链表是否相同

❗特别注意：

  • 前半部分的链表与后半部分的链表，当有一个链表遍历完后，就结束了

✊动图示例：

在这里插入图片描述

🔥此处我们便可以复用上面题目的代码

👉实现：

structListNode*middleNode(structListNode* head){structListNode* fast = head;structListNode* slow = head;while(fast !=NULL&& fast->next !=NULL){
        slow = slow->next;
        fast = fast->next->next;}return slow;}

structListNode*reverseList(structListNode* head){structListNode* cur = head;structListNode* newhead =NULL;while(cur){//即不断取结点下来，头插到NULL前面去structListNode* next = cur->next;
        
        cur->next = newhead;

        newhead = cur;

        cur = next;}return newhead;}

bool isPalindrome(structListNode* head){//1.找中间节点structListNode* mid =middleNode(head);//2.逆置中间往后的部分链表structListNode* rHead =reverseList(mid);while(head && rHead){if(head->val == rHead->val){
            head = head->next;
            rHead = rHead->next;}else{return false;}}return true;}

🏷️ 相交链表【难度：简单】

🔍题目传送门：
Leetcode：160. 相交链表
给你两个单链表的头节点 

headA

和 

headB

，请你找出并返回两个单链表相交的起始节点

如果两个链表不存在相交节点，返回 

null

示例：

这里是引用

💡解题关键：

  • 链表的相交是不会只相交于一个结点的（交点为同一个地址的结点），而是会从交点处往后的链表都重合
  • 本题目的关键：两个链表是否相交，若相交，求交点

➡️思路一：

  • 两层循环遍历链表a与链表b,判断a中是否有一个结点的地址等于b链表中的某个结点地址
  • 只要有一个，就是相交

❗特别注意：

  • 此方法的时间复杂度为：O(N*M)
  • 我们还可以继续优化

➡️思路二：

  • 直接各自走到两个链表的最后一个结点位置，判断那个结点地址是否相同：若相同则相交，否则不相交
  • 若相交，则找交点：- 1️⃣求出两个链表各自的长度，求出长度的差距gap- 2️⃣让相对较长的链表先遍历gap步- 3️⃣然后两个链表同时往后遍历，直到第一个地址相同的结点，就是交点

✊动图示例：

  • 第一步：判断是否相交在这里插入图片描述
  • 第二步：若相交，则判断交点在这里插入图片描述

🔥特殊情况：

  • 要注意判断两个链表是否为NULL链表，只要有一个是空链表，就不满足相交，就可以直接返回NULL

👉实现：

structListNode*getIntersectionNode(structListNode* headA,structListNode*headB){if(headA ==NULL|| headB ==NULL){returnNULL;}structListNode* curA = headA;structListNode* curB = headB;int lenA =0;int lenB =0;while(curA){
        curA = curA->next;
        lenA++;}while(curB){
        curB = curB->next;
        lenB++;}//1.判断是否相交if(curA != curB){returnNULL;}structListNode* longList = headA;structListNode* shortList = headB;if(lenB > lenA){
        longList = headB;
        shortList = headA;}int gap =abs(lenB - lenA);//求绝对值//2.走差距步while(gap--){
        longList = longList->next;}//3.同时走[此时剩下得一定是相交得]while(longList && shortList){if(longList == shortList){return longList;}else{
            longList = longList->next;
            shortList = shortList->next;}}returnNULL;}

🌟总结

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

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

感谢你们的阅读😆

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

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

✨如果觉得收获满满，可以点点赞👍支持一下哟~✨
在这里插入图片描述

标签： 链表 面试 算法
本文转载自: https://blog.csdn.net/qq_62817113/article/details/124673953
版权归原作者 Dream_Y.Ocean 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构与算法】8道链表面试真题超详剖析，带你领略算法思想【附思路、动图、源码】”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

249基于java ssm springboot安全生产培训管理系统学习课件（源码+文档+运行视频+讲解视频）

【Linux庖丁解牛】—软件安装&vim！

【花雕学编程】Arduino LVGL 之在不同平台创建相同的用户界面

基于电商大数据的商品推荐系统

UE5.4像素流及前端接入

Unity中接入讯飞语音（实时语音转写）WebAPI（非SDK）

springboot实现获取客户端IP地址

文章导航