链表简单1 种解法
#LCR140训练计划 II
返回链表倒数第 cnt 个节点；该旧文件对应 LCR 140，而不是 LeetCode 140“单词拆分 II”。
#链表#双指针
原题
给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号对应的节点。
示例 1：
输入：head = [2,4,7,8], cnt = 1 输出：8
提示：
1 <= head.length <= 1000 <= head[i] <= 1001 <= cnt <= head.length
解题主线
- 让 fast 先走 cnt 步，再与 slow 同速移动；fast 到 null 时 slow 就是目标节点。
- 该技巧本质上维持 fast 与 slow 之间固定为 cnt 个节点的间隔。
解法 1：固定间距双指针
fast 先前进 cnt 次，随后 fast、slow 同步前进到 fast 为空。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode trainingPlan(ListNode head, int cnt) {
// cnt 必须为正且不超过链长，否则无法建立固定间距。
if (cnt <= 0) throw new IllegalArgumentException("cnt must be positive");
ListNode fast = head;
ListNode slow = head;
// fast 先走 cnt 步，建立两个指针之间固定为 cnt 个节点的间距。
for (int i = 0; i < cnt; i++) {
if (fast == null) throw new IllegalArgumentException("cnt exceeds list length");
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}实现提示
- 在题目保证 1 <= cnt <= 链表长度时不会抛出异常。
边界与易错点
- 旧实现对 cnt 大于链长会空指针，对 cnt <= 0 也没有定义；展示代码统一拒绝非法输入。
- 编号应写作 LCR140，不能依据文件名 QL140 误归为普通 LeetCode 140。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
QL140_kNodeFromEnd.java