当前位置：首页 > article >正文

【LeetCode】数据结构题解（3）[查找链表中倒数第k个节点]

article 2025/3/5 3:13:12

查找链表种倒数第k个节点

1.题目来源
2.题目描述
3.解题思路
4.代码展示

所属专栏：玩转数据结构题型
博主首页：初阳785
代码托管：chuyang785
感谢大家的支持，您的点赞和关注是对我最大的支持！！！
博主也会更加的努力，创作出更优质的博文！！
关注我，关注我，关注我，重要的事情说三遍！！！！！！！！

1.题目来源

查找链表中倒数第k个节点

2.题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点

在这里插入图片描述

3.解题思路

这个和之前的查找链表中间节点的题型有点像，可以说是升级版的的吧。
但是我们的解题思路还是有点不一样的。

我们的思路还是定义一个快慢指针（如果有小伙伴不知道快慢指针的可以去我的专栏玩转数据结构题型中的解题（2）中有讲解到）fast和low。
既然我们要找到倒数第k个数的话，我们不妨先让fast走k步，走完后我们的fast和low一起走，等到我们fast结束后，我们的low就找到了我们的倒数第k个节点。

在这里插入图片描述

fast先走k步。

走完后fast和low一起走，fast=NULL的时候停止，这个时候low就找到了倒数第k个位置的节点。

4.代码展示

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{

    struct ListNode *fast=head,*low=head;
    //先让fast走k步
    while(k--)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    //fast和low一起走
    while(fast)
    {
        low=low->next;
        fast=fast->next;
    }
    return low;
}