参考资料：

[1]剑指OFFER课本 P135

关键词：

第n-k+1个节点、先走再一起走

常规解法：

先走完一遍，再走

高级解法（背住）：

倒数第1个节点，两个指针差0，先走0步，然后一起走
倒数第2个节点，两个指针差1，先走1步，然后一起走
倒数第3个节点，两个指针差2，先走2步，然后一起走

自己的解法：

改进版：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    
        if (pListHead == nullptr)
            return nullptr;

        ListNode* pNode = pListHead;
        int nLen=0;
        //步骤1：先看链表有几个节点
        while (pNode != nullptr)
        {
            nLen++;
            pNode = pNode->next;
        }

        if (nLen < k)
            return nullptr;
        //步骤2：从头到尾找到该节点
        int nIndexForward = nLen - k;
        pNode = pListHead;
        while (nIndexForward--)
        {
            pNode = pNode->next;
        }
        return pNode;
    }

};

初始版：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    
        //思路：
        //思路1：长度为n的链表，倒数第一个节点是n,倒数第二个节点是n-1,所以倒数第k个节点是n-k+1
        //思路2：定义两个指针，倒数第一个节点，两个指针差0，两个指针一起走。倒数第二个节点，两个指针差1，两个指针一起走
        //所以倒数第k个节点，两个指针差k-1,然后一起走.
        
        //思路1
        
        //步骤1：统计链表的长度
        ListNode* pNode = pListHead;
        int len=0;
        while(pNode!=nullptr)
        {
            pNode = pNode->next;
            len++;
        }
        //异常情况得写上
        if(pListHead == nullptr||len<k)
            return nullptr;
        
        //步骤2：输出倒数第K个节点
        //不确定，拿个实例来说话，比如1 2  倒数第1个节点，第2-1+1个节点，循环执行1次
        pNode = pListHead;//记得弄起点！！！
        for(int i=1;i<(len-k+1);i++)
        {
            pNode = pNode->next;
        }
        return pNode;
        
        /*
        //思路2：
        //步骤1:定义2个指针
        ListNode* pNode1 = pListHead;
        ListNode* pNode2 = pListHead;
        if(pNode1 == nullptr)
            return nullptr;
        
        //步骤2：倒数第1个节点。先走1步，倒数第2个节点，先走2步，倒数第k个节点，先走k步。XXXXX错误的思路
        //怎么把len给考虑进去啊
        //倒数第1个节点，两个指针差0，不用先走。倒数第2个节点，两个指针差1，1个指针先走一步。背住！！！！！！给实例验证。比如1 
        for(int i=1;i<=k-1;i++)
        {
             pNode1 = pNode1->next;
             if(pNode1 == nullptr)
                 return nullptr;
        }
        
        //步骤2:2个指针一起走
        while(pNode1->next != nullptr)
        {
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode2;
        */
    }

};

标准答案：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    
        //创建2个指针
        ListNode* pList1;
        ListNode* pList2;
        
        pList1 = pListHead;
        pList2 = pListHead;
        
        if(pListHead ==nullptr || k ==0)
            return nullptr;
        //k=1的时候不执行
        //2个指针，访问导数第一个指针，两个指针差0,访问倒数第2个指针，两个指针差1
        //1.
        for(int i = 1;i<=k-1;i++)
        {
            pList1 = pList1->next;
            //如果pList1指向的为空，返回
            if(pList1 == nullptr)
                return nullptr;
        }
        //2.两个指针一起访问
        while(pList1->next != nullptr)
        {
            pList1 = pList1->next;
            pList2 = pList2->next;
        }
        
        return pList2;
        
    }
};