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

解题思路：

    首先：由于链表不能倒着遍历，所以无法通过倒遍历的方法得到倒数第k个节点。这里我们采取双指针的方法来求。

步骤：

    1. 让快慢指针都指向头节点，然后循环k步，让快指针走到k+1个节点，此时，快慢指针之间的距离为k。

    2. 当快指针不为空时，让快慢指针同时向后走，直到快指针为空时，慢指针的位置就是倒数第k个元素的位置。

        因为，从后往前看：NULL为起始看，最后一个节点的位置是倒数第2，slow的位置是倒数k+1；而从最后一个位置看，最后一个位置就是倒数第1，而slow的位置就是倒数k

    

代码如下：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        //采用双指针的方法，先让快指针走到距离表头k的位置上，然后让慢指针指向表头
        //最后快慢指针以相同的速度向后走，当快指针到达尾部时，慢指针的位置就是所求位置。
        ListNode* fast = pHead;
        ListNode* slow = pHead; //慢指针在第一个节点
        //快指针先走k步,到达第K+1个节点
        for(int i = 0; i < k; i++){
            if(fast != nullptr)   //达不到k步，说明链表过短，没有倒数k
                fast = fast->next;
            else
                return nullptr;
        } //for循环结束时，fast,slow之间相差k个位置
        //当fast走到nullptr时，slow的位置就是倒数第k个节点的位置
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;  //返回节点位置
    }
};