連結清單中的倒數第k個節點

題目：輸入一個連結清單，輸出該連結清單的倒數第k個節點。從1開始計數，即連結清單的尾節點為倒數第1個節點。

解答：首先自然想到的是尋找倒數第k個節點，那麼就是從前往後數第n-k+1個節點，則先對連結清單周遊一遍得到連結清單的長度，然後第二次周遊時走n-k+1步就可以了。但是該方法需要對連結清單周遊兩次，有沒有隻需要周遊依次的方法？自然是有的，可以想到用兩個指針的方法，先讓第一個指針先走k-1步，然後第二個指針指向連結清單的第1個節點，然後兩個指針同時往後走，當第二個指針達到尾節點時，第一個指針指向的正是倒數第k個節點。

struct Node{
	int m_data;
	Node* m_pNext;
	Node(const int data = 0,Node* next = NULL):m_data(data),m_pNext(next){}
};

Node* FindKthNodeToTail(Node* pHead,const int k)
{
	if(!pHead || k <= 0)
		return NULL;

	Node* pFirstNode = pHead;
	Node* pSecondNode = pHead;
	for(int index = 0; index < k-1; ++index)
	{
		if(NULL == pFirstNode->m_pNext)//防止k大于連結清單長度
			return NULL;
		pFirstNode = pFirstNode->m_pNext;
	}
	while(pFirstNode->m_pNext)
	{
		pFirstNode = pFirstNode->m_pNext;
		pSecondNode = pSecondNode->m_pNext;
	}
	return pSecondNode;
}