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

链表中倒数第K个节点

article 2025/3/28 6:07:49

题目：

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

示例 1：

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

思路：

使用双指针方法，第一个指针先走cnt步，然后一起走，先走的指针走到末尾，后走的指针走的倒数第cnt第位置。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* trainingPlan(struct ListNode* head, int cnt) 
{
    //处理空链表
    if(NULL == head)
    {
        return NULL;
    }
    struct ListNode* p1 = head;
    struct ListNode* p2 = head;
    //先让p1走cnt步
    for(int i = 0;i < cnt; i++)
    {
        p1 = p1->next;
    }
    //p1 和 p2一起走n-cnt步
    while(p1 != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    //p1走到末尾，p2到达到倒数cnt的位置
    return p2;
}

代码分析：

1. 初始化两个指针
struct ListNode* p1 = head;  // 快指针
struct ListNode* p2 = head;  // 慢指针
p1 和 p2 最初都指向链表头节点 head。

2. 快指针 p1 先走 cnt 步
for (int i = 0; i < cnt; i++)
{
    p1 = p1->next;
}
让 p1 向前移动 cnt 步，此时 p1 和 p2 之间相隔 cnt 个节点。

示例：
链表 1 → 2 → 3 → 4 → 5，cnt = 2：
p1 移动到 3，p2 仍在 1，两者间隔 2 个节点。

3. 同步移动 p1 和 p2
while (p1 != NULL)

{
    p1 = p1->next;
    p2 = p2->next;
}
同时移动 p1 和 p2，直到 p1 到达链表末尾（NULL）。

此时 p2 会指向倒数第 cnt 个节点（因为 p1 和 p2 始终相隔 cnt 步）。

4. 返回结果

return p2; // p2 指向倒数第 cnt 个节点

5. 关键点分析

p1 先走 cnt 步后，p1 和 p2 之间形成固定间隔 cnt。

当 p1 走到末尾时，p2 自然落后 cnt 步，即倒数第 cnt 个节点。