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

那首先，最简单的做法是首先遍历一遍链表，得到链表的结点总个数（长度）为n，之后将指向队首的指针向后移动n-k+1次即可得倒数第k个结点。但是这样呢，需要遍历链表两次，并不是很满意。
则其次设定双指针，二者同时指向队首。第一个指针首先移动k-1次，之后两个指针同时开始移动，当第一个指针到达链表尾部时，刚好第二个指针指向倒数第k个结点。(倒数第k个结点到头结点之间的距离为n-k，尾部到第一个结点之间的距离为n-1。则第一个指针移动k-1次，距离尾部结点距离为n-k。则第一个指针从此处到达尾部结点，要移动n-k次，那么若此时第二个指针从头部往后移动，也会移动n-k次，即刚好到达倒数第k个结点。)
需要注意的是: 1.所给头结点为空指针，那么其没有倒数第k个结点，返回NULL
             2.所给k为0，因为倒数从1开始计数，则不存在第0个结点，返回NULL
             3.链表总长小于k(第一个指针后移k-1时判断),则无倒数第k个结点，返回NULL

/**
 * 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) {

        if (pHead == nullptr || k == 0) // 判断头结点是否为空，k是否为0
            return NULL;

        ListNode* first = pHead;
        ListNode* last = pHead;

        unsigned int n = k - 1;
        while (n != 0) {
            if (first->next == NULL) // 判断链表长度是否大于等于k
                return NULL; // 若链表长度小于k，返回NULL
            else 
                first = first->next;
            n--;
        }
        while (first != NULL && first->next != NULL) {
            first = first->next;
            last = last->next;
        }
        return last;
    }
};