题解 | 链表中倒数最后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类
     * 空间复杂度O(1)的做法，使用快慢指针，双指针，两个指针相距k个位置，当后面的指针移动到队尾的时候
     * 第一个指针所指的位置，就是要求解的倒数第K的位置，就跟滑动窗口一样，很妙的搞法，一般要求空间复杂度为1的时候优先
     * 想到的就是快慢指针
     ** fast = 1, slow=1, posLeft = 0 
     ** fast = 2, slow=1, pos = 1 
     *  fast = 3, slow=1, pos=2
     *  fast = 4, slow =2, pos = 2
     *  fast = 5, slow =3, pos =2
     *  fast = null, slow =4, pos = 2
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (k ==0 || pHead == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        int posLeft = 0;
        while(fast != null) {
            if (posLeft < k) {
               posLeft++;
               fast = fast.next;
            } else {
               fast = fast.next;
               slow = slow.next;
            }
        }
        if (posLeft == k) {
            return slow;
        } else {
            return null;
        }
       
    }

    public ListNode FindKthToTailOn(ListNode pHead, int k) {
        if (k == 0) {
            return null;
        }
        List<ListNode> arr = new ArrayList<>();
        ListNode current = pHead;
        while (current != null) {
            arr.add(current);
            current = current.next;
        }
        if (k > arr.size()) {
            return null;
        }
        return arr.get(arr.size() - k);
    }
}

看到空间复杂度是O1，就需要联想到双指针的搞法