题目难度：简单

题目描述：

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。 数据范围：$0\le n\le 10^{5}0\le n\le 10^5$ ，$0\le a_i\le 10^{9}0\le a\_i\le 10^9$，$0\le k\le 10^{9}0\le k\le 10^9$ 要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例1：

输入：{1,2,3,4,5},2 返回值：{4,5} 说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。

思路1:使用额外的数据结构储存节点的信息

• 写法一：使用哈希表 运行时间：31ms 占用内存：8804KB

class Solution {
public:
  	ListNode* FindKthToTail(ListNode* pHead, int k) {
      	int len = 0;
      	unordered_map<int, ListNode*> hashNode;
      
      	while(pHead) {
          	len++;
          	hashNode.insert({len, pHead});
          	pHead = pHead->next;
        }
      
      	if(k > len) return nullptr;
      	else return hashNode[len - k + 1];
    }
}

• 写法二：使用vector 运行时间：26ms 占用内存：6580KB（PS：不知道为啥会快一点）

class Solution {
public:
  	ListNode* FindKthToTail(ListNode* pHead, int k) {
      	int len = 0;
      	vector<ListNode*> hashNode;
      
      	while(pHead) {
          	len++;
          	hashNode.push_back(pHead);
          	pHead = pHead->next;
        }
      
      	if(k > len) return nullptr;
      	else return hashNode[len - k];
    }
}

• 写法三：使用栈 运行时间：25ms 占用内存：5536KB

calss Solution {
public:
  	ListNode* FindKthToTail(ListNode* pHead, int k) {
      	if(!pHead) return nullptr;
      	stack<ListNode*> stk;
      
      	while(pHead) {
          	stk.push(pHead);
          	pHead = pHead->next;
        }
      
      	k -= 1;
      	while(!stk.empty() && k > 0) {
          	stk.pop();
          	k--;
        }
      
      	if(stk.empty() && k >= 0 || !stk.empty() && k < 0) return nullptr;
      	else return stk.top();
    }
}

空间复杂度可优化成O(1)： 时间复杂度：O(n)，空间复杂度：O(1) 运行时间：25ms 占用内存：5168KB

class Solution {
public:
  	ListNode* FindKthToTail(ListNode* pHead, int k) {
      	int len = 0;
      	ListNide* dummyHead = head;
      
      	while (dummyHead) {
          	len++;
          	dummyHead = dummyHead->next;
        }
      
      	if(len < k || k == 0) return nullptr;
      
      	int i = len - k;
      	while (i--) pHead = pHead->next;
      
      	return pHead;
    }
}

思路2:快慢指针

运行时间：26ms 占用内存：5172KB

class Solution {
public:
  	ListNode* FindKthToTail(ListNode* pHead, int k) {
      	if(k == 0 || !pHead) return nullptr;
      
      	ListNode* faster = pHead;
      	ListNode* slower = pHead;
      
      	while(k--) {
          	if(faster) faster = faster->next;
          	else slower = nullptr;
      }
      
      	while(faster) {
          	faster = faster->next;
          	slower = slower->next;
        }
      
      	return slower;
    }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘