C++算法输出链表倒数第k个元素

C++算法输出链表倒数第k个元素

链表结点定义如下：&nbsp&nbsp

struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};

/*-----------------------------
Copyright by yuucyf. 2011.05.08
------------------------------*/
#include "stdafx.h"
#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct S_ListNode
{
  T m_nKey;
  S_ListNode* m_pNext;
  S_ListNode()
  {
	  m_pNext = NULL;
  }
};
template <class T>
S_ListNode<T>* ReverseList(S_ListNode<T>* psHead)
{
    if (!psHead || !(psHead->m_pNext)) return psHead;
    
    S_ListNode<T>* psPrev = NULL;
    while (psHead)
    {
        S_ListNode<T> * psTemp = psHead;
        psHead = psHead->m_pNext;
        psTemp->m_pNext = psPrev;
        psPrev = psTemp;
    }
    return psPrev;
}
template <class T>
void BuildSList(S_ListNode<T>* &psRet, int nSize)
{
	assert(nSize > 0);
	S_ListNode<T>* psHead = new S_ListNode<T>;
	assert(NULL != psHead);
	psHead->m_nKey = nSize;
	psRet = psHead;
	while (--nSize)
	{
		S_ListNode<T> *psTemp = new S_ListNode<T>;
		assert(NULL != psTemp);
		psTemp->m_nKey = nSize;
		psHead->m_pNext = psTemp;
		psHead = psHead->m_pNext;
	}
}
template <class T>
void OutputNodeValue(int nK, const S_ListNode<T> *psHead)
{
	int nIndex = nK;
	while (nIndex-- && psHead)
	{
		psHead = psHead->m_pNext;
	}
	if (psHead)
		cout << "链表倒数第" << nK << "个数为" << psHead->m_nKey << endl ;
}
int _tmain(int argc, _TCHAR* argv[])
{
	S_ListNode<int> *psHead = NULL;
	BuildSList(psHead, 10);
	psHead = ReverseList(psHead);
	OutputNodeValue(2, psHead);
	return 0;
}

别人有用递归算法进行的逆排序。

/*-----------------------------
Copyright by leeyunce. 
Modified by yuucyf . 2011.05.08
------------------------------*/
template<typename T>
S_ListNode<T>* ReverseListRecursive(S_ListNode<T>* psHead)
{
    if (!psHead|| !(psHead->m_pNext)) return psHead;
    S_ListNode<T>* psRet = ReverseListRecursive(psHead->m_pNext);
    psHead->m_pNext->m_pNext = psHead;
    psHead->m_pNext = NULL;
    return psRet;
}