凡科做的是网站吗,建筑工程项目管理软件,建站公司兴田德润,wordpress logo制作#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;数据结构、算法模板 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 #x1f4cb;前言一. ⛳️链表的中间结点二. ⛳️链表中倒数第k个结点#x1f4dd;结语 #x1f4c… 个人主页聆风吟 系列专栏数据结构、算法模板 少年有梦不应止于心动更要付诸行动。 文章目录 前言一. ⛳️链表的中间结点二. ⛳️链表中倒数第k个结点结语 前言 hello! 小伙伴们大家好哇今天作者给大家带来的是链表的相关面试题的讲解在学习了下文之后相信大家可以更好的理解链表并且我们同过本文的练习相信大家对快慢双指针也将会有一定的了解。 系列专栏本期文章收录在《剑指offer每日一练》大家有兴趣可以浏览和关注后面将会有更多精彩内容 欢迎大家关注点赞收藏⭐️留言 一. ⛳️链表的中间结点
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
题目 给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。
示例 输入 head [1,2,3,4,5] 输出 [3,4,5] 解释 链表只有一个中间结点值为 3 限制
链表的结点数范围是 [1, 100]1 Node.val 100
解题思路 暴力求解不推荐 拿到本题我们很容易想到一种方法就是遍历整个链表记录整个链表的元素个数count然后求出中间结点的位数cout/2 1最后从头开始遍历链表到cout/2 1位置的结点返回该结点即可。显然该方法是比较慢的那么有没有更好的方法呢当然是有的我们可以借助快慢双指针进行快速求解。
快慢双指针推荐 创建快慢双指针 slow 和 fast 分别指向链表的头部循环执行
快指针 fast 每轮走两步慢指针 slow 每轮走一步
这样 fast 的步数恒为 slow 的 2 倍因此当快指针遍历完链表时慢指针就指向链表中间节点。而由于长度为偶数的链表有两个中间节点因此需要分两种情况考虑
链表的长度为奇数当 fast 走到链表的尾结点时slow 正好是中间结点链表的长度为偶数当 fast 为空越过尾结点时slow 正好走到第二个中间结点。 总结以上规律应在当 fast 遇到或越过尾节点时跳出循环并返回 slow 即可。
示例动图展示
c代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针struct ListNode* slow head, *fast head;//循环执行while(fast fast-next){slow slow-next;fast fast-next-next;}//返回中间结点return slow;
}二. ⛳️链表中倒数第k个结点
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
题目 输入一个链表输出该链表中倒数第k个结点。
示例 输入 1,{1,2,3,4,5} 输出 {5} 解题思路 快慢双指针 学习了上题相信大家对快慢双指针已经有了一定了解。本题我们可以先创建快慢双指针 slow 和 fast 分别指向链表的头部
先让快指针fast 先向后走k 步 注意当fast向后走的过程中fast提前为空说明链表的长度没有 k 大需要终止程序返回结果NULL。然后快指针fast 和慢指针slow 一起循环向后走直到fast为空时终止循环返回slow即可。
示例动图展示
c代码
/*** struct ListNode {* int val;* struct ListNode *next;* };*//*** * param pListHead ListNode类 * param k int整型 * return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code here//创建快慢双指针 slow 和 fast 分别指向链表的头部struct ListNode* slow pListHead, *fast pListHead;//先让快指针fast 先向后走 k 步for(int i 0; i k; i){//如果fast提前为空需要终止程序返回结果NULLif(fast NULL){return NULL;}fast fast-next;}//快指针fast 和慢指针slow 一起循环向后走//fast为空时终止循环while(fast){slow slow-next;fast fast-next;}//返回return slow;
}结语 今天的干货分享到这里就结束啦如果觉得文章还可以的话希望能给个三连支持一下聆风吟的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是作者前进的最大动力
