题解 | #链表中倒数最后k个结点#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
         if (pHead == null || k <= 0) {
            return null;
        }
        
        ListNode slow = pHead;
        ListNode fast = pHead;
        
         // 先让fast指针移动k步
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return null; // 链表长度小于k，返回null
            }
            fast = fast.next;
        }
        
        // 然后同时移动slow和fast指针，直到fast指针到达链表末尾
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow; // 此时slow指向倒数第k个节点
    }
}

这个问题的思路是使用快慢指针来实现在单链表中找到倒数第 k 个节点。具体的步骤如下：

1. 创建两个指针，一个称为 slow，另一个称为 fast。初始化它们都指向链表的头节点。
2. 让 fast 指针先向前移动 k 步。这样，fast 指针就领先 slow 指针 k 个节点。
3. 同时移动 slow 和 fast 指针，直到 fast 指针到达链表的末尾。由于 fast 指针领先 slow 指针 k 个节点，当 fast 指针到达末尾时，slow 指针就会指向倒数第 k 个节点。
4. 返回 slow 指针所指向的节点。

这种方法的关键在于初始化时先让 fast 指针领先 k 个节点，然后同步移动两个指针，使它们的距离保持为 k，这样当 fast 指针到达末尾时，slow 指针就会指向倒数第 k 个节点。

这个思路适用于空间复杂度 O(n) 和 O(1) 的两种实现方式。在空间复杂度 O(1) 的实现方式中，我们不需要使用额外的数据结构来存储节点，只需要两个指针即可。