几种实现链表逆序的方法

链表逆序就是把一个链表按照原来的链接顺序逆序实现（也就是将头变成尾，尾变成头）。

编程思路：其实最关键的是先通过原来的链接顺序找到下个节点，然后再把前个节点反序。

链表的头节点如下：

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

常规实现：

ListNode* ReverseIteratively(ListNode* pHead)
{
	ListNode* pReversedHead = NULL;
	ListNode* pNode = pHead;
	ListNode* pPrev = NULL;
	while(pNode != NULL)
	{
		// get the next node, and save it at pNext
		ListNode* pNext = pNode->m_pNext;

   		// if the next node is null, the currect is the end of original
  		// list, and it's the head of the reversed list
    	if(pNext == NULL)
     		pReversedHead = pNode;

    	// reverse the linkage between nodes
    	pNode->m_pNext = pPrev;

   		// move forward on the the list
    	pPrev = pNode;
  		pNode = pNext;
   	}
}

递归实现（不需要临时节点）：

ListNode* reverse_list( ListNode* head)       //逆序
{
	ListNode* new_head=head;
	if(head==NULL || head->next==NULL)
		return head;
	new_head = reverse_list(head->next);
	head->next->next=head;
	head->next=NULL; 	//防止链表成为一个环，这是最关键的。
	return new_head; 
}