【数据结构与算法】返回单链表的倒数第 k 个节点

举报
倔强的石头_ 发表于 2025/09/05 21:27:47 2025/09/05
【摘要】 实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。 方法一:计数器方式 先遍历链表,求出链表长度count。倒数第k个节点,就是正数第count-k+1个节点。再次遍历链表,找到该节点,返回数据 方法二:双指针方式 定义两个指针slow和fast,初始都指向第一个节点 初始fast指针先走k步,然后slow指针和fast指针每次各走一步,当fast指针指向空时,slow指针所指向的节

目录

一、问题描述

二、解题思路

方法一:计数器方式

方法二:双指针方式

三、C语言代码实现

方法一:计数器方式

方法二:双指针方式



一、问题描述


二、解题思路

方法一:计数器方式

  • 最多遍历两次链表
  • 时间复杂度  O  (n)
  • 空间复杂度  O(1)
  • 先遍历链表,求出链表长度count
  • 倒数第k个节点,就是正数第count-k+1个节点(下标为count-k)
  • 再次遍历链表,找到该节点,返回数据


方法二:双指针方式

  • 最多遍历一次链表
  • 时间复杂度  O  (n)
  • 空间复杂度  O(1)
  • 定义两个指针slow和fast,初始都指向第一个节点
  • 初始fast指针先走k步
  • 然后slow指针和fast指针每次各走一步,当fast指针指向空时,slow指针所指向的节点就是倒数第k个节点
  • 返回该节点的数据

 1.快慢指针初始位置

2.快指针先走k步

3.快指针走到NULL,慢指针走到倒数第k个节点


三、C语言代码实现

方法一:计数器方式

//返回单链表的倒数第 k 个节点
struct ListNode {
    int val;
    struct ListNode* next;
};
typedef struct ListNode ListNode;

//方式一 计数器方式
int kthToLast1(struct ListNode* head, int k)
{
    ListNode* pcur = head;//遍历节点的指针
    int count = 0;
    while (pcur)//求出链表长度
    {
        pcur = pcur->next;
        count++;
    }
    pcur = head;
    count = count - k;
    while (count--)//找到该节点
    {
        pcur = pcur->next;
    }
    return pcur->val;
}


方法二:双指针方式

//方式二 快慢指针方式
int kthToLast2(struct ListNode* head, int k)
{
    ListNode* slow = head, * fast = head;
    while (k--)//快指针先走k步
    {
        fast = fast->next;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}


【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。