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

题意思路：

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

方法一:双指针
定义两个指针，i和j指向链表的头结点。

i指针先走k步，如果链表的长度也等于k的话，快指针走k步正好会走到空。

如果在走第k步之前链表就指向空的话，说明链表长度小于k，直接返回空。

然后i指针和j指针一起走，当i指针指向空的时候，j指针指向的就是倒数第k个节点，返回j指针结果。

复杂度分析

时间复杂度：O(N)，N链表的长度，遍历链表。

空间复杂度：O(1)未开辟新空间

图文详解：

代码：

/**
 * 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==NULL)return pHead;//若链表为空则返回为空
        ListNode* i = pHead;//定义指针i和j都指向链表第一个数字
        ListNode* j = pHead;
        while(k--){//i指针先走k步
            if(i==NULL)return NULL;//如果在走第k步之前链表就指向空的话，说明链表长度小于k，直接返回空。
            i=i->next;
        }
        while(i!=NULL){//然后i指针和j指针一起走，当i指针指向空的时候，j指针指向的就是倒数第k个节点，返回j指针结果。
            i=i->next;
            j=j->next;
        }
        return j;
    }
};

方法二：栈
先将链表的所有元素遍历并存放在栈中
然后根据栈的先进后出的特性将栈中元素遍历得到答案

复杂度分析

时间复杂度：O(N)，N链表的长度，遍历链表。

空间复杂度：O(N)，链表存储与读取数据

代码：

/**
 * 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==NULL)return pHead;//若链表为空则返回为空
        ListNode* i = pHead;//定义指针i指向链表第一个数字
        stack<ListNode*> res;//利用栈的先进后出的性质存放元素
        while(i!=NULL){
            res.push(i);
            i=i->next;
        }
        if(res.size()<k)return NULL;//特判为空
        ListNode *ans=NULL;
        while(k--){
            ans=res.top();//得到最后k个元素
            res.pop();
        }
        return ans;
    }
};