题目描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。

**题解1：使用双指针，fast指向第k个节点，slow指向第一个节点 //此时，fast后面的节点个数为链表长度-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
       ListNode * fast = pHead,*slow = pHead;
       for(int i=0;i<k;i++){//fast先指向第k个结点
           if(fast ==NULL)
               return NULL;
           fast = fast->next;
       }
       while(fast){//一直循环，直到fast指向最尾端。
           fast = fast->next;
           slow = slow->next;//slow和fast仪器运动
       }
       return slow;
   }
};

题解2：使用辅助数组

ListNode* FindKthToTail(ListNode* pHead, int k) {
    vector<ListNode*> v;
    ListNode* temp = pHead;
    while (temp) {
        v.push_back(temp);
        temp = temp->next;
    }
    if (v.size() < k)
        return NULL;
    return v[v.size() - k];
}