- 描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围：0≤n≤10^5，0≤ai≤10^9，0≤k≤10^9
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
- 示例1
输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。
- 示例2
输入：{2},8
返回值：{}
- 算法思想
方法1：
先计算链表长度len,再正序寻找倒数第k个节点，即寻找第len-k+1个节点。
方法2：
双指针法。
1、准备一个快指针，从链表头开始，在链表上先走k步。
2、准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
3、快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
- 代码
1 /** 2 * struct ListNode { 3 * int val; 4 * struct ListNode *next; 5 * ListNode(int x) : val(x), next(nullptr) {} 6 * }; 7 */ 8 class Solution { 9 public: 10 /** 11 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 12 * 13 * 14 * @param pHead ListNode类 15 * @param k int整型 16 * @return ListNode类 17 */ 18 ListNode* FindKthToTail(ListNode* pHead, int k) { 19 //方法一 20 //计算链表长度 21 // ListNode *p=pHead; 22 // int len=0; 23 // while(p){ 24 // len++; 25 // p=p->next; 26 // } 27 // if(k>len) return nullptr; 28 // //寻找倒数第k个节点 29 // int n=len-k+1; 30 // p=pHead; 31 // for(int i=0;i<n-1;i++) 32 // p=p->next; 33 // return p; 34 35 //方法二 36 ListNode* fast = pHead; 37 ListNode* slow = pHead; 38 //快指针先行k步 39 for (int i = 0; i < k; i++) { 40 if (fast != nullptr) 41 fast = fast->next; 42 //达不到k步说明链表过短，没有倒数k 43 else 44 return nullptr; 45 } 46 //快慢指针同步，快指针先到底，慢指针指向倒数第k个 47 while(fast!=nullptr){ 48 fast = fast->next; 49 slow = slow->next; 50 } 51 return slow; 52 } 53 };