正文

leetcode刷题笔记之链表篇剑指offer22.链表中倒数第k个节点(代码片段)

大家好我叫张同学  大家好我叫张同学  2023-03-09  450

关键词：

😈博客主页：🐼大家好我叫张同学🐼
💖 欢迎点赞 👍 收藏 💗留言 📝 欢迎讨论！ 👀
🎵本文由【大家好我叫张同学】原创，首发于 CSDN 🌟🌟🌟
✨精品专栏（不定时更新）【数据结构+算法】【做题笔记】【C语言编程学习】
☀️ 精品文章推荐
【C语言进阶学习笔记】三、字符串函数详解（1）（爆肝吐血整理，建议收藏！！！）
【C语言基础学习笔记】+【C语言进阶学习笔记】总结篇（坚持才有收获！）

前言

为什么要写刷题笔记？
写博客的过程也是对自己刷题过程的梳理和总结，是一种耗时但有效的方法。
当自己分享的博客帮助到他人时，又会给自己带来额外的快乐和幸福。
（刷题的快乐+博客的快乐，简直是奖励翻倍，快乐翻倍有木有QAQ🙈）

题目内容

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有6个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3个节点是值为 4 的节点。

原题链接（点击跳转）

遍历链表法

单链表要求倒数第k个结点，由于结点之间关系的单向性，并不好直接求。但是如果我们将倒数转化为顺数，那么仅需要从头节点开始遍历链表便可轻松实现，具体过程看图解。

算法图解

函数实现

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
    int length = 0;//求链表长度
    struct ListNode* cur = head;
    while(cur)
        length++;
        cur = cur->next;
    
    cur = head;//cur重新返回头节点
    int step = length-k;//第length+1-k个位置只需要向后走length-k步
    while(step--)
        cur = cur->next;
    
    return cur;

注意：leetcode题目中默认k的大小是小于length的长度。若实际中这个条件未给出，那么我们则需要加上以下条件判断的代码：

 if(k > length)
        return NULL;

比如在牛客网中没有这个判断就无法通过，会提示你段错误。

加上判断语句后

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
    // write code here
    int length = 0;//求链表长度
    int step = 0;
    struct ListNode* cur = pListHead;
    while(cur)
        length++;
        cur = cur->next;
    
    if(k > length)
        return NULL;
    cur = pListHead;//cur重新返回头节点
    step = length-k;//第length+1-k个位置只需要向后走length-k步
    while(step--)
        cur = cur->next;
    
    return cur;

快慢指针法

我们还可以用快慢指针法来求链表中倒数第k个结点，可以先让快指针fast先走k步，然后快慢指针（fast、slow）一起往后走，当快指针fast走到最后的NULL位置时，慢指针刚好走到倒数第k个位置。

算法图解

函数实现

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
    struct ListNode *fast = head,*slow = head;
    while(k--)//fast先走k步
        fast = fast->next;
    
    while(fast)//fast、slow一起往后走
        fast = fast->next;
        slow = slow->next;
    
    return slow;

如果是在牛客网上做这道题目，那么我们使用快慢指针法的时候，还需要多考虑一些边界的情况，对上述代码进行相应调整如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
    struct ListNode *fast = pListHead,*slow = pListHead;
    if(k == 0)//这里加了k=0的条件判断
        return NULL;
    while(k--)//fast先走k步
        if(fast == NULL)//这里加了fast提前走到NULL的判断
        return NULL;
        fast = fast->next;
    
    while(fast)//fast、slow一起往后走
        fast = fast->next;
        slow = slow->next;
    
    return slow;

leetcode刷题笔记之链表篇234.回文链表(代码片段)

😈博客主页：🐼大家好我叫张同学🐼💖欢迎点赞👍收藏💗留言📝欢迎讨论！👀🎵本文由【大家好我叫张同学】原创，首发于CSDN🌟🌟🌟✨精品专栏（不定时更新... 查看详情

leetcode刷题笔记之链表篇206.反转链表(代码片段)

leetcode刷题笔记之链表篇141.环形链表(代码片段)

leetcode刷题笔记之链表篇160.相交链表(代码片段)

leetcode刷题笔记之链表篇142.环形链表ii(代码片段)

leetcode刷题笔记之链表篇21.合并两个有序链表(代码片段)

leetcode刷题笔记之链表篇面试题02.04.分割链表(代码片段)

leetcode刷题笔记之链表篇141.环形链表(代码片段)

数据结构学习笔记二线性表之链表篇（双向链表）(代码片段)

...以考察出同学们的水平和能力呀~）。如果我们经常在leetcode或者牛客网等刷题网站上面玩耍& 查看详情

leetcode刷题100天—剑指offer22.链表中倒数第k个节点(链表)—day26(代码片段)

前言：作者：神的孩子在歌唱大家好，我叫运智剑指Offer22.链表中倒数第k个节点难度简单259收藏分享切换为英文接收动态反馈输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开... 查看详情

leetcode刷题100天—剑指offer22.链表中倒数第k个节点(链表)—day26(代码片段)

leetcodejava刷题笔记—剑指offer22.链表中倒数第k个节点(代码片段)

剑指Offer22.链表中倒数第k个节点输入一个链表，输出该链表中倒数第k个节点。简单难度。使用快慢指针即可，快指针先走k步，然后快慢一起走，直到快指针走到最后一个节点，此时慢指针即指向倒数k个节点... 查看详情

leetcode刷题第一周(代码片段)

LeetCode刷题第一周剑指Offer22.链表中倒数第k个节点165.比较版本号面试题17.14.最小K个数704.二分查找278.第一个错误的版本35.搜索插入位置剑指Offer10-I.斐波那契数列977.有序数组的平方189.旋转数组283.移动零1221.分割平衡字符串1167.两... 查看详情

剑指offer之链表(代码片段)

//剑指offer之链表//面试题6从尾到头打印链表/*****************************************************************************************问题描述：输入一个链表的头节点，从尾到头反过来打印出每个节点的值链表节点定义如下：structListNodeintm_nValue;Lis... 查看详情

力扣(leetcode)剑指offer刷题笔记（java），已完结！！！(代码片段)

文章目录3、数组中重复的数字4、二维数组中的查找5、替换空格6、从尾到头打印链表7、重建二叉树9、两个栈来实现一个队列10-1、斐波那契数列10-2、跳台阶11、旋转数组的最小数字12、矩阵中的路径13、机器人的运动范围14-1、剪... 查看详情

剑指offer刷题记录

Leetcode上新加入了剑指offer板块，最近准备这些题重新做一遍，温故知新。后续会将所有的解题思路和代码收录到这里，并将这些题做分类，便于以后查阅。数组剑指offer——数组篇字符串剑指offer——字符串篇链表、栈与队列剑... 查看详情

算法leetcode剑指offer22.链表中倒数第k个节点（多语言实现）(代码片段)

文章目录剑指Offer22.链表中倒数第k个节点：样例1：分析题解rustgotypescriptpythoncc++java原题传送门：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/剑指Offer22.链表中倒数第k个节点：查看详情