【数据结构与算法】8道链表面试真题超详剖析,带你领略算法思想【附思路、动图、源码】
💛 前情提要💛
本章节是数据结构
的链表
的相关基础题目
讲解~
以下的内容一定会让你对链表
相关知识的题目,有一个颠覆性的认识哦!!!
❗以下内容以C语言
的方式实现❗
以下内容干货满满,跟上步伐吧~
作者介绍:
🎓 作者: 热爱编程不起眼的小人物🐐
🔎作者的Gitee:代码仓库
📌系列文章&专栏推荐: 《刷题特辑》、 《C语言学习专栏》、《数据结构_初阶》📒我和大家一样都是初次踏入这个美妙的“元”宇宙🌏 希望在输出知识的同时,也能与大家共同进步、无限进步🌟
📌导航小助手📌
- 👉前情提要
- 📒面试真题【全面深度解析】
- 🏷️ 移除链表元素【难度:简单】
- 🏷️ 反转链表【难度:简单】
- 🏷️ 链表的中间结点【难度:简单】
- 🏷️ 链表中倒数第k个结点【难度:简单】
- 🏷️ 合并两个有序链表【难度:简单】
- 🏷️ 分割链表【难度:简单】
- 🏷️ 回文链表【难度:简单】
- 🏷️ 相交链表【难度:简单】
- 🌟总结
👉前情提要
-
大家可以跟着本文的题目讲解进行
链表
相关知识的复习&加深- 若大家对
链表
还不太熟悉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
一起挪动
✊动图示例:
👉实现:
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
语句,程序结束
🏷️ 反转链表【难度:简单】
🔍题目传送门:
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
或者只有一个元素的时候,就不需要反转
了
👉实现:
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
链表的情况
🏷️ 链表的中间结点【难度:简单】
🔍题目传送门:
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️⃣
慢指针
:一次走一步
-
✊动图示例:
👉实现:
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个结点【难度:简单】
🔍题目传送门:
剑指 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
链表,直接结束程序
👉实现:
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;}
🏷️ 合并两个有序链表【难度:简单】
🔍题目传送门:
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
,就无需合并,可以直接返回另外一个链表
👉实现:
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;}
🏷️ 分割链表【难度:简单】
🔍题目传送门:
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
),则在链接后的新链表中就指向了前面的某个结点,形成闭环,无法结束
👉实现:
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;}
🏷️ 回文链表【难度:简单】
🔍题目传送门:
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️⃣此时虽然没有正真地断开链表,但我们可以将中间结点后半部分逆置的链表看作新的链表,继而比较此链表与前半部分的链表是否相同
❗特别注意:
- 前半部分的链表与后半部分的链表,当有一个链表遍历完后,就结束了
✊动图示例:
🔥此处我们便可以复用上面题目的代码
👉实现:
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;}
🏷️ 相交链表【难度:简单】
🔍题目传送门:
Leetcode:160. 相交链表 |
---|
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点
如果两个链表不存在相交节点,返回 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;}
🌟总结
综上,我们基本了解了数据结构中的 “链表重要面试真题” 🍭 的知识啦~~
恭喜你的内功又双叒叕得到了提高!!!
感谢你们的阅读😆
后续还会继续更新💓,欢迎持续关注📌哟~
💫如果有错误❌,欢迎指正呀💫
✨如果觉得收获满满,可以点点赞👍支持一下哟~✨