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

题目难度：中等
题目考察：链表
题目内容：输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。

题目分析：
首先一个链表不遍历一遍无法知道长度，所以这题时间复杂度最低是O(n),并且题目要找到倒数第k个数，如果我们知道了链表有n个数，倒数第k个实际上就是正数第n-k+1个。

算法1：遍历
正数第n-k个就很容易找出了，只需要遍历一遍数组即可
下面要考虑链表长度小于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) {
        // write code here
        int idx=0,kk=0;
        //idx记录链表长度，kk记录正数第几个数
        ListNode *ans=pHead;
        //先记录下头节点
        while(pHead)
        {
            idx++;
            pHead=pHead->next;
            //指向下一个，idx加1
        }
        //这时候链表长度是idx
        while(ans)
        {
            kk++;
            //此时ans是正数第kk个节点
            if(kk==idx-k+1)
            {
                //找到了第idx-k+1个数则返回
                return ans;
            }
            ans=ans->next;
        }
        //上面如果找不到第idx-k+1会跳出，输出空链表即可
        return NULL;
    }
};

算法2：构造
下面给出另外一种解法，可以直接将链表的数填入vector中，将最后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) {
        // write code here
        //当链表为空时
        if(pHead==nullptr) return nullptr;

        //先把各个结点装入数组中
        vector<ListNode*> result;
        while(pHead!=nullptr){
            result.push_back(pHead);
            pHead=pHead->next;
        }
        //如果K大于链表的长度
        if(k>result.size()) return nullptr;
        //直接返回
        return result[result.size()-1-(k-1)];
    }
};