LCR 140.训练计划 II

难度：🟢 简单

标签：链表、双指针

链接：LCR 140. 训练计划 II (剑指 Offer 22. 链表中倒数第k个节点)

题目描述

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

示例 1：

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

解题思路

核心思想

本题的目标是在一次遍历中找到链表的倒数第 k 个节点。核心思想是利用两个指针的固定距离差来定位目标节点。

思路选择

快慢指针法 是解决此问题的最优思路。它通过一次遍历就解决了问题，空间复杂度为 O(1)。

• 我们设置两个指针，fast 和 slow，都从头节点开始。

• 先让 fast 指针向前移动 k 步。此时，fast 和 slow 之间就相隔了 k 个节点。

• 然后，同时移动 fast 和 slow 指针，每次都移动一步。

• 当 fast 指针到达链表的末尾（即 fast 为 null）时，slow 指针所在的位置正好就是倒数第 k 个节点。

关键步骤

1. 初始化：创建两个指针，fast 和 slow，都指向头节点 head。

2. 拉开距离：让 fast 指针先向前移动 cnt 步。

3. 同步移动：同时向前移动 fast 和 slow 指针，直到 fast 指针到达链表末尾 (fast === null)。

4. 返回结果：当循环结束时，slow 指针指向的就是目标节点，返回 slow。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} cnt
 * @return {ListNode}
 */
var trainingPlan = function (head, cnt) {
    let fast = head, slow = head;

    // 快指针先走 cnt 步
    while (cnt > 0) {
        fast = fast.next;
        cnt--;
    }

    // 快慢指针同步走，直到快指针到达终点
    while(fast !== null){
        fast = fast.next;
        slow = slow.next;
    }

    // 此时慢指针指向倒数第 cnt 个节点
    return slow;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是链表的长度。我们只需要对链表进行一次完整的遍历。

• 空间复杂度：O(1) 我们只使用了 fast 和 slow 两个额外指针，空间消耗是恒定的。

相关题目

• 0019.删除链表的倒数第N个结点

• 0141.环形链表

总结

本题是双指针（特别是快慢指针）技巧在链表问题中的经典应用。通过巧妙地设置两个指针的初始距离，可以非常优雅地解决“倒数第 k 个节点”这类问题，避免了需要两次遍历（一次获取长度，一次查找）的麻烦。