C语言反转单向链表

反转单向链表分为递归和非递归两种方式。递归的实现方式比较简单，而非递归实现效率较高，在面试时应注意边界条件。
这道题在面试时被要求现场作答的概率还是很大的，比较tricky的地方就是要在当前条件下保存好next of next的指针，如果一时想不起来程序怎么写，可以先自己画个图看看。

// ReverseList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
enum{N = 3};
class Node
{
public:
	Node* pNext;
	int var;
	Node(int i):pNext(NULL), var(i){}
};
void helper(Node* pHead, Node*& reverseHead)
{
	if(pHead->pNext->pNext != NULL)
		helper(pHead->pNext, reverseHead);
	else
		reverseHead = pHead->pNext;
	pHead->pNext->pNext = pHead;
}
Node* ReverseList(Node* pHead)
{
	if(NULL == pHead || NULL == pHead->pNext)
		return NULL;
	Node* reverseHead = NULL;
	helper(pHead, reverseHead);
	pHead->pNext = NULL;
	return reverseHead;
}
Node* ReverseListNonRecursive(Node* pHead)
{
	if(NULL == pHead || NULL == pHead->pNext)
	{
		return NULL;
	}
	Node* N1 = pHead->pNext;
	Node* N2 = pHead->pNext->pNext;
	
	if(NULL == N2)
	{
		N1->pNext = pHead;
		pHead->pNext = NULL;
	}
	else
	{
		Node* t = pHead;
		while (NULL != N2)
		{
			N1->pNext = pHead;
			pHead = N1;
			N1 = N2;
			N2 = N2->pNext;
		}
		N1->pNext = pHead;
		t->pNext = NULL;
	}
	return N1;
}
void PrintNode(Node* pHead)
{
	while (pHead != NULL)
	{
		printf("%d ",pHead->var);
		pHead = pHead->pNext;
	}
	printf("\r\n");
}
void Test()
{
	Node* pHead = new Node(0);
	Node* pNode = pHead;
	for(int i = 1; i < N; i++)
	{
		Node* pNext = new Node(i);
		pNode->pNext = pNext;
		pNode = pNode->pNext;
	}
	PrintNode(pHead);
	//Node* reversedHead = ReverseListNonRecursive(pHead);
	Node* reversedHead = ReverseList(pHead);
	PrintNode(reversedHead);
}
int _tmain(int argc, _TCHAR* argv[])
{
	Test();
	return 0;
}