【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点

这篇具有很好参考价值的文章主要介绍了【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点,剑指offer每日一练,链表,数据结构,c语言
🌈个人主页:聆风吟
🔥系列专栏:数据结构、算法模板
🔖少年有梦不应止于心动,更要付诸行动。


📋前言

    💬 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位置的结点,返回该结点即可。显然该方法是比较慢的,那么有没有更好的方法呢?当然是有的,我们可以借助快慢双指针进行快速求解。

快慢双指针(推荐)
创建快慢双指针 slowfast 分别指向链表的头部,循环执行:

  • 快指针 fast 每轮走两步
  • 慢指针 slow 每轮走一步

这样 fast 的步数恒为 slow 的 2 倍,因此当快指针遍历完链表时,慢指针就指向链表中间节点。而由于长度为偶数的链表有两个中间节点,因此需要分两种情况考虑:

  • 链表的长度为奇数:当 fast 走到链表的尾结点时,slow 正好是中间结点;
  • 链表的长度为偶数:当 fast 为空(越过尾结点)时,slow 正好走到第二个中间结点。

【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点,剑指offer每日一练,链表,数据结构,c语言
总结以上规律,应在当 fast 遇到或越过尾节点时跳出循环,并返回 slow 即可。

示例动图展示:【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点,剑指offer每日一练,链表,数据结构,c语言

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}

解题思路:
快慢双指针
学习了上题相信大家对快慢双指针已经有了一定了解。本题我们可以先创建快慢双指针 slowfast 分别指向链表的头部:

  1. 先让快指针fast 先向后走k 步;
    注意:当fast向后走的过程中,fast提前为空,说明链表的长度没有 k 大,需要终止程序,返回结果NULL。
  2. 然后快指针fast 和慢指针slow 一起循环向后走;
  3. 直到fast为空时终止循环,返回slow即可。

示例动图展示:【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点,剑指offer每日一练,链表,数据结构,c语言

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提前为空,需要终止程序,返回结果NULL
        if(fast == NULL)
        {
            return NULL;
        }

        fast = fast->next;
    }

    //快指针fast 和慢指针slow 一起循环向后走
    //fast为空时终止循环
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }

    //返回
    return slow;
}


📝结语

     今天的干货分享到这里就结束啦!如果觉得文章还可以的话,希望能给个三连支持一下,聆风吟的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的最大动力!
【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点,剑指offer每日一练,链表,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-754051.html

到了这里,关于【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode】链表的中间节点|链表中倒数第k个节点

    目录 1.链表的中间节点 2.链表中倒数第k个节点  思路1:遍历链表,统计节点个数count,返回第count/2 +1个节点  📖Note: 注意循环条件为--mid,--mid循环执行mid-1次,mid--循环mid次,返回的是中间节点的下一个节点 思路二:快慢指针 设置一个慢指针slow,一个快指针fast,慢指针一

    2024年02月15日
    浏览(34)
  • 【代码随想录 | Leetcode | 第六天】链表 | 反转链表 | 两两交换链表中的节点 | 删除链表的倒数第 N 个结点

    欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来反转链表、两两交换链表中的节点和删除链表的倒数第N个节点的分享 ✨ ✨题目链接点这里 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例 1: 示例 2: 示例 3: 提示: 链表中节点的数

    2024年02月16日
    浏览(58)
  • 【Leetcode】移除链表元素 链表的中间节点 链表中倒数第k个节点

    目录 一.【Leetcode203】移除链表元素 1.链接 2.题目再现  A.双指针法 B.类尾删法 C.哨兵位 二.【Leetcode876】链表的中间节点 1.链接:链表的中间节点 2.题目再现 3.解法:快慢指针 三.链表中倒数第k个节点 1.链接:链表中倒数第k个节点 2.题目再现 3.解法 :快慢指针 1.链接 移除链表

    2024年02月01日
    浏览(65)
  • 算法刷题Day4 两两交换链表中的节点+删除链表的倒数第N个结点+链表相交+环形链表

    使用dummy节点可以极大地简化过程 有个地方折磨了我有一会儿,是粗心导致的,而且提示的错误也很难发现是哪里导致的。就是在case为 head = [1], n = 1 时,最后释放了 tmp 之后(此时 tmp 刚好指向 head ,我还 return head; ,意思就是操作了已经被我释放的内存, leetcode 就报错了

    2024年02月09日
    浏览(49)
  • 【剑指offer|图解|链表】删除链表的节点 + 训练计划 V

    🏠 个人主页:@聆风吟的个人主页 🔥系列专栏:本期文章收录在专栏《剑指offer每日一练》中,大家有兴趣可以浏览和关注,后面将会持续更新更多精彩内容! ⏰寄语:少年有梦不应止于心动,更要付诸行动。 🎉欢迎大家关注🔍点赞👍收藏⭐️评论📝 🌈作者留言:文章

    2024年02月08日
    浏览(51)
  • 【力扣-JZ22】链表中倒数第k个结点

    🖊作者 : Djx_hmbb 📘专栏 : 数据结构 😆今日分享 : \\\"把手插进米堆的原因 \\\" : 因为米堆类似于高密度的流体,会给人的手带来较大的压强,这种压强促进静脉血回流,会让人感到生理上的舒服。 【力扣-JZ22】 : 先计算链表有多长,然后length–,找到第k个指针 : fast指针先走k步,然后

    2024年02月01日
    浏览(65)
  • 【数据结构OJ题】链表中倒数第k个结点

    原题链接:https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13tqId=11167rp=2ru=/activity/ojqru=/ta/coding-interviews/question-ranking 目录 1. 题目描述 2. 思路分析 3. 代码实现 快慢指针法   (如果有小伙伴不了解快慢指针法,可以看看这篇文章:https://blog.csdn.net/m0_62531913/article/details/

    2024年02月12日
    浏览(50)
  • HJ51 输出单向链表中倒数第k个结点

    写在前面: 做题环境如下: 题目渠道:牛客网 HJ51 输出单向链表中倒数第k个结点 华为机试题 编程语言:C++ 描述 输入一个单向链表,输出该链表中倒数第k个结点,链表的倒数第1个结点为链表的尾指针。 链表结点定义如下: 正常返回倒数第k个结点指针,异常返回空指针

    2024年02月02日
    浏览(42)
  • LeetCode | 19. 删除链表的倒数第 N 个结点

    OJ链接 思路: 定义虚拟头节点 dummy 并初始化使其指向 head 然后定义快慢指针 让快指针先走n步 然后一起走 最后删除倒数第n个节点 然后释放虚拟节点 dummy

    2024年02月04日
    浏览(75)
  • LeetCode:19. 删除链表的倒数第 N 个结点

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 来源:力扣(LeetCode) 难度: 中等 提示: 链表中结点的数目为 sz 1 = sz = 30 0 = Node.val = 100 1 = n = sz 示例

    2024年02月02日
    浏览(74)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包