15：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
? 示例：
给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是我们从链表结点的定义可以看出本题中的链表是单向链表，单向链表的结点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通。
方法一： 遍历两次
思路：既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n个结点，那么倒数第k个结点就是从头结点开始的第n-k+1个结点。如果我们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n-k+1步就可以了。如何得到结点数n，这个不难，只需要从头开始遍历链表，每经过一一个结点，计数器加1就行了。也就是说我们需要遍历链表两次，第一次统计出链表中结点的个数，第二次就能找到倒数第k个结点。
代码语言：cpp
/**
* 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) {
if(k == 0|| head == NULL) //防止输入为空指针和k-1为0xFFFFFFFF
return NULL;
int n = 0;
ListNode* phead = head;
while(head){ //遍历一次确定结点个数
head = head->next;
n++;
}
head = phead;
for(int i = 0; i < n - k; i++) //倒数第k个结点就是从头结点开始的第n-k+1个结点
if(head->next != NULL) //输入的链表结点个数少于k在for循环中会空指针程序崩溃
head = head->next;
return head;
}
};208?/?208?个通过测试用例
状态：通过
执行用时:?4 ms
内存消耗:?10.3 MB
方法二： 双指针法
但是当我们把这个思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次。
为了实现只遍历链表一次就能找到倒数第k个结点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动;从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第-一个(走在前面的)指针到达链表的尾结点时，第二个指针(走在后面的)指针正好是倒数第k个结点。
下面以在有6个结点的链表中找倒数第3个结点为例分析这个思路的过程。首先用第一一个指针从头结点开始向前走两(2= 3-1)步到达第3个结点(如图3.5 (a)所示)。接着我们把第二个指针初始化指向链表的第一个结点(如图3.5 (b)所示)。最后让两个指针同时向前遍历，当第一个指针到达链表的尾结点时，第二个指针指向的刚好就是倒数第3个结点(如图3.5 (c)所示)。
?
?代码语言：cpp
/**
* 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) {
if(head == NULL || k==0) //防止输入为空指针和k-1为0xFFFFFFFF
return NULL;
ListNode* pAhead = head; //A指针
for(unsigned int i = 0; i<k-1; ++i){ //在A走k-1次，AB指针开始一块走
if(pAhead->next!=NULL) //输入的链表结点个数少于k在for循环中会空指针程序崩溃
pAhead = pAhead->next;
else{
return NULL;
}
}
ListNode* pBehind = head; //B指针
while(pAhead->next!=NULL){ //A指针到达尾结点，此时B指针正好时倒数第k个结点
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}
};?208?/?208?个通过测试用例
状态：通过
执行用时:?8 ms
内存消耗:?10.2 MB