写点什么

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

作者:Dream-Y.ocean
  • 2022 年 9 月 27 日
    广东
  • 本文字数:7211 字

    阅读完需:约 24 分钟

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

前情提要


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


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


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


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



👉前情提要

  • 大家可以跟着本文的题目讲解进行链表相关知识的复习 &加深

  • 若大家对链表还不太熟悉 or 需要回顾一下基本知识,可点击单链表带头+双向+循环链表至相关文章进行回顾

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



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

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

题目传送门:


给你一个链表的头节点 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一起挪动


动图示例:



👉实现:


struct ListNode* removeElements(struct ListNode*head, int val){    struct ListNode* cur = head;    struct ListNode* prev = NULL;        //边走边删除     //直至cur走到NULL就停止    while (cur)     {        //要删除结点时:        if (cur->val == val)        {                    struct ListNode* 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语句,程序结束



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

题目传送门:


给你单链表的头节点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或者只有一个元素的时候,就不需要反转


👉实现:


struct ListNode* reverseList(struct ListNode* head){    if (head == NULL || head->next == NULL)    {        return head;    }
struct ListNode* n1 = NULL; struct ListNode* n2 = head; struct ListNode* 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,即可达反转的效果


动图示例:



特别注意:


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


👉实现:


struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head; struct ListNode* newhead = NULL;
while (cur) { //即不断取结点下来,头插到NULL前面去 struct ListNode* next = cur->next; cur->next = newhead;
newhead = cur;
cur = next;
} return newhead;}
复制代码


补充:


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



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

题目传送门:


给定一个头结点为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️⃣慢指针:一次走一步


动图示例:



👉实现:


struct ListNode* middleNode(struct ListNode* head){    struct ListNode* fast = head;    struct ListNode* slow = head;
while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; }
return slow;}
复制代码



🏷️ 链表中倒数第 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链表,直接结束程序


👉实现:


struct ListNode* getKthFromEnd(struct ListNode* head, int k){    struct ListNode* fast = head;    struct ListNode* slow = head;
//fast先走k步 while (k--) { //如果k还没走完,fast就为NULL了 if (fast == NULL) { //说明K比链表长度都要长 //也说明 链表可能为空 return NULL; }
fast = fast->next; }
//再同时走 //fast为NULL的时候结束 while (fast) { slow = slow->next; fast = fast->next; } return slow;}
复制代码



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

题目传送门:


将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的


示例 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️⃣当某一链表已遍历完,而另外一链表没遍历完的时候,直接将其剩下的尾插到新链表上


特别注意:


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


动图示例:



🔥特别情况:


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


👉实现:


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){    struct ListNode* l1 = list1;    struct ListNode* l2 = list2;
if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; }
struct ListNode* head = NULL; struct ListNode* 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;}
复制代码



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

题目传送门:


给你一个链表的头节点 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),则在链接后的新链表中就指向了前面的某个结点,形成闭环,无法结束


👉实现:


struct ListNode* partition(struct ListNode* head, int x){    struct ListNode* lessHead = NULL;    struct ListNode* lessTail = NULL;    struct ListNode* greaterHead = NULL;    struct ListNode* greaterTail = NULL;        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));    greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next = NULL; greaterTail->next = NULL;
struct ListNode* 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;}
复制代码



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

题目传送门:


给你一个单链表的头节点 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️⃣此时虽然没有正真地断开链表,但我们可以将中间结点后半部分逆置的链表看作新的链表,继而比较此链表与前半部分的链表是否相同


特别注意:


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


动图示例:



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


👉实现:


struct ListNode* middleNode(struct ListNode* head){    struct ListNode* fast = head;    struct ListNode* slow = head;
while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; }
return slow;}
复制代码


struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head; struct ListNode* newhead = NULL;
while (cur) { //即不断取结点下来,头插到NULL前面去 struct ListNode* next = cur->next; cur->next = newhead;
newhead = cur;
cur = next;
} return newhead;}
复制代码


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



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

题目传送门:


给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点


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


示例:



💡解题关键:


  • 链表的相交是不会只相交于一个结点的(交点为同一个地址的结点),而是会从交点处往后的链表都重合

  • 本题目的关键:两个链表是否相交,若相交,求交点


➡️思路一:


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

  • 只要有一个,就是相交


特别注意:


  • 此方法的时间复杂度为:O(N*M)

  • 我们还可以继续优化


➡️思路二:


  • 直接各自走到两个链表的最后一个结点位置,判断那个结点地址是否相同:若相同则相交,否则不相交

  • 若相交,则找交点

  • 1️⃣求出两个链表各自的长度,求出长度的差距gap

  • 2️⃣让相对较长的链表先遍历gap

  • 3️⃣然后两个链表同时往后遍历,直到第一个地址相同的结点,就是交点


动图示例:


  • 第一步:判断是否相交

  • 第二步:若相交,则判断交点


🔥特殊情况:


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


👉实现:


struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode *headB){    if (headA == NULL || headB == NULL)    {        return NULL;    }

struct ListNode* curA = headA; struct ListNode* curB = headB;
int lenA = 0; int lenB = 0;
while (curA) { curA = curA->next; lenA++; }
while (curB) { curB = curB->next; lenB++; }
//1.判断是否相交 if (curA != curB) { return NULL; }
struct ListNode* longList = headA; struct ListNode* 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; } } return NULL;}
复制代码



🌟总结

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


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


感谢你们的阅读:satisfied:


后续还会继续更新:heartbeat:,欢迎持续关注:pushpin:哟~


如果有错误❌,欢迎指正呀


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


发布于: 刚刚阅读数: 3
用户头像

Dream-Y.ocean

关注

还未添加个人签名 2022.06.17 加入

还未添加个人简介

评论

发布
暂无评论
【数据结构与算法】8道链表面试真题超详剖析,带你领略算法思想【附思路、动图、源码】_链表_Dream-Y.ocean_InfoQ写作社区