题目的主要信息：

• 一个长度为$nn$的链表，返回原链表中从倒数第k个结点至尾节点的全部节点
• 如果该链表长度小于k，请返回一个长度为 0 的链表
• 要求：时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$，进阶要求空间复杂度$O(1)O(1)$

方法一：先找长度再找最后k

具体做法：

我们可以先遍历一次链表找到链表的长度，然后比较链表长度是否比k小，如果比k小返回一个空链表，否则遍历n-k次即可找到所求。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        int n = 0;
        ListNode* p = pHead;
        while(p != NULL){ //统计链表长度
            n++;
            p = p->next;
        }
        if(n < k) //长度过小，返回空链表
            return p = NULL;
        p = pHead;
        for(int i = 0; i < n - k; i++) //遍历n-k次
            p = p->next;
        return p;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最坏情况下两次遍历$nn$个元素
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：快慢双指针

具体做法：

我们准备快慢双指针，都从链表头出发，快指针先行k步，达不到k步说明链表过短，返回空链表。然后快慢指针同步向后，快指针先到底，慢指针指向倒数第k个，因为它们之间差了k个元素。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        int n = 0;
        ListNode* fast = pHead; 
        ListNode* slow = pHead;
        for(int i = 0; i < k; i++){  //快指针先行k步
            if(fast != NULL)
                fast = fast->next;
            else //达不到k步说明链表过短，返回空链表
                return slow = NULL;
        }
        while(fast != NULL){ //快慢指针同步，快指针先到底，慢指针指向倒数第k个
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，总共遍历$nn$个链表元素
• 空间复杂度：$O(1)O(1)$，无额外空间使用