LeetCode-剑指 Offer 22. 链表中倒数第k个节点（C语言）

目录捏

一、题目描述
二、示例与提示
三、思路
四、代码

一、题目描述

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

二、示例与提示

示例 1：

输入： head = [2,4,7,8], cnt = 1
输出： 8

提示

1 <= head.length <= 100
0 <= head[i] <= 100
1 <= cnt <= head.length

三、思路

本题第一时间想到的解法：

遍历统计链表长度，记为 n
设置一个指针走 (n−cnt) 步，即可找到链表倒数第 cnt 个节点

在这里插入图片描述

后来发现使用双指针则可以不用统计链表长度（k 即 cnt）：

设置快慢指针皆指向链表头结点
快指针先走 cnt 步
快慢指针共同移动，直至快指针走过链表尾节点时跳出（跳出后，慢指针即指向倒数第 cnt 个节点）
返回慢指针即可

四、代码

struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    struct ListNode* fast = head, *slow = head;
    // 快指针先走cnt步
    while (cnt--)
    fast = fast->next;
    // 快慢指针共同移动，直至快指针走过链表尾节点
    while (fast) {
        fast = fast->next;
        slow = slow->next; // 此时慢指针指向倒数第cnt个节点
    }
    // 返回慢指针即可
    return slow;
}