输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
有了上一题 jz24.md 的经验，本题不搞花里胡哨的递归，想到啥开始码啥，辅助栈一遍过！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
stack<ListNode*> s;
ListNode* cur=head;
while(cur!=NULL){
s.push(cur);
cur=cur->next;
}
while(k>1){
k--;
s.pop();
}
return s.top();
}
};
仔细想一下，这也是暴力，空间复杂度不行，而且为哈要用栈，都给出来k了数组不香吗。评论区有一个写法，改进一下变成这样：
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
int len=0;
ListNode* p=head;
while(p!=NULL){
p=p->next;
len++;
}
ListNode** arr=new ListNode*[len];
int id=0;
while(head!=NULL){
arr[id++]=head;
head=head->next;
}
return arr[len-k];
}
};
还有用了vector的，但测试下来效率却与stack没有明显区别，他们还是都归为一类吧——笔试方案。
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
vector<ListNode*> res;
while(head!=NULL)
{
res.push_back(head);
head=head->next;
}
return res[res.size()-k];
}
};高级的解法中，被提到最多的，称为——快慢指针。
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode former = head, latter = head;//1.赋值
for(int i = 0; i < k; i++) {//2.快指针先走k步
if(former == null) return null;//不够k个元素，数组越界情况
former = former.next;
}
while(former != null) {//3.快慢指针一起走，维护一个k的长度，直到快指针走到终点
former = former.next;
latter = latter.next;
}
return latter;//4.慢指针即为所求
}
}
作者：jyd，注释：Keenster时间复杂度 O(N)： N 为链表长度；总体看， former 走了 N 步， latter 走了 (N-k)步。 空间复杂度 O(1)： 双指针 former , latter 使用常数大小的额外空间。