题目：输入一个链表，输出链表中倒数第k个节点，为了符合大多数人的习惯，本题从1开始计数，即链表的尾巴节点是倒数第一个节点。

方法1：先遍历链表得到链表的个数n，倒数第k个节点就是n-k+1再遍历一次链表，找到第n-k+1个节点就是倒数第k个节点；这种方法遍历两次链表；

方法2：先遍历链表把链表压入一个栈，再出栈，第k次出栈就是第k个节点；

方法3：先反转链表，再遍历

方法4：定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1；第二个指针保持不动，从第k步开始，第二个指针也开始遍历，两个指针差距k-1个距离

，当第一个指针走到了尾巴节点，第二个指针正好在倒数第k个节点；

代码：

ListNode* FindKthFromTail(ListNode* pListHead,int k){	if (pListHead == NULL || k == 0)//防止空的链表  和 k值 等于 0 的情况	{		return NULL;	}	ListNode* pAhead = pListHead;	ListNode* pBehind = NULL;	for (int i = 0; i < k-1; i++)	{		if (pAhead->m_pNext != NULL)		{			pAhead = pAhead->m_pNext;		}		else		{			return NULL;		}	}	pBehind = pListHead;	while(pAhead->m_pNext != NULL)	{				pAhead  = pAhead->m_pNext;		pBehind = pBehind->m_pNext;	}	return pBehind;}

完整代码：

// FindKthFromTail.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;struct ListNode {	int       m_nValue;	ListNode* m_pNext;	ListNode(int k):m_nValue(k),m_pNext(NULL)	{	}};ListNode* FindKthFromTail(ListNode* pListHead,int k){	if (pListHead == NULL || k == 0)//防止空的链表  和 k值 等于 0 的情况	{		return NULL;	}	ListNode* pAhead = pListHead;	ListNode* pBehind = NULL;	for (int i = 0; i < k-1; i++)	{		if (pAhead->m_pNext != NULL)		{			pAhead = pAhead->m_pNext;		}		else		{			return NULL;		}	}	pBehind = pListHead;	while(pAhead->m_pNext != NULL)	{				pAhead  = pAhead->m_pNext;		pBehind = pBehind->m_pNext;	}	return pBehind;}int _tmain(int argc, _TCHAR* argv[]){	ListNode* head  = new ListNode(1);	ListNode* Node1 = new ListNode(2);	ListNode* Node2 = new ListNode(3);	ListNode* Node3 = new ListNode(4);	ListNode* Node4 = new ListNode(5);	ListNode* Node5 = new ListNode(6);	ListNode* Node6 = new ListNode(7);	head->m_pNext = Node1;	Node1->m_pNext = Node2;	Node2->m_pNext = Node3;	Node3->m_pNext = Node4;	Node4->m_pNext = Node5;	Node5->m_pNext = Node6;	Node6->m_pNext = NULL;	ListNode* p = FindKthFromTail(head,3);	cout<<p->m_nValue<<endl;	getchar();	return 0;}

C++算法之 链表中倒数第k个节点