链表简单1 种解法

#LCR140训练计划 II

返回链表倒数第 cnt 个节点；该旧文件对应 LCR 140，而不是 LeetCode 140“单词拆分 II”。

#链表#双指针

解题主线

让 fast 先走 cnt 步，再与 slow 同速移动；fast 到 null 时 slow 就是目标节点。

该技巧本质上维持 fast 与 slow 之间固定为 cnt 个节点的间隔。

解法 1：固定间距双指针

fast 先前进 cnt 次，随后 fast、slow 同步前进到 fast 为空。

时间复杂度

O(n)

空间复杂度

O(1)

LCR140. 训练计划 II · 固定间距双指针

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode trainingPlan(ListNode head, int cnt) {
        if (cnt <= 0) throw new IllegalArgumentException("cnt must be positive");
        ListNode fast = head;
        ListNode slow = head;
        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;
    }
}

fast 先前进 cnt 次，随后 fast、slow 同步前进到 fast 为空。

在题目保证 1 <= cnt <= 链表长度时不会抛出异常。

边界与易错点

旧实现对 cnt 大于链长会空指针，对 cnt <= 0 也没有定义；展示代码统一拒绝非法输入。
编号应写作 LCR140，不能依据文件名 QL140 误归为普通 LeetCode 140。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

QL140_kNodeFromEnd.java