反转链表

/*********************************************************
题目：定义一个函数输入一个链表的头结点，反转该链表并输出反转
后链表的头结点。
**********************************************************/

#include<iostream>
#include<stdio.h>
using namespace std;
struct ListNode
{
	int m_nValue;
	ListNode* pNext;
};

ListNode* createListNode(int value)
{
	ListNode* pNewNode = new ListNode();
	pNewNode->m_nValue = value;
	pNewNode->pNext = NULL;
	return pNewNode;
}

void connectListNode(ListNode* pNode1, ListNode* pNode2)
{
	if(pNode1 == NULL || pNode2 == NULL)
		return;
	pNode1->pNext = pNode2;
}
//反转链表
ListNode* reverseList(ListNode* pHead)
{
	if(pHead == NULL)		//无效输入
		throw exception("Invalid input!");


	ListNode* pNode = pHead;		//当前节点
	ListNode* pPrev = NULL;			//pNode前一节点
	ListNode* pReversedNode = NULL;	//反转后起始节点

	while(pNode != NULL)
	{
		ListNode* pNext = pNode->pNext;
		if(pNext == NULL)
			pReversedNode = pNode;
		pNode->pNext = pPrev;;
		pPrev = pNode;
		pNode = pNext;
	}
	return pReversedNode;
}

//打印链表
void printList(ListNode* pHead)
{
	if(pHead == NULL)
		printf("NULL");
	while(pHead != NULL)
	{
		printf("%d\t",pHead->m_nValue);
		pHead = pHead->pNext;
	}
	printf("\n");
}
//单元测试
//空节点
void test1()
{
	reverseList(NULL);
}
//一个节点
void test2()
{
	ListNode* pHead = createListNode(5);
	ListNode* pNewHead =  reverseList(pHead);
	printList(pNewHead);
}
//一般情况
void test3()
{
	ListNode* pNode1 = createListNode(1);
	ListNode* pNode2 = createListNode(2);
	ListNode* pNode3 = createListNode(3);
	ListNode* pNode4 = createListNode(4);

	connectListNode(pNode1,pNode2);
	connectListNode(pNode2,pNode3);
	connectListNode(pNode3,pNode4);

	ListNode* pNewHead = reverseList(pNode1);
	printList(pNewHead);
}

int main()
{
	try
	{
		test2();
		test3();
		test1();
	}
	catch(exception ex)
	{
		cout<<ex.what();
	}
	return 0;
}

反转链表,布布扣,bubuko.com

反转链表

原文：http://blog.csdn.net/walkerkalr/article/details/20999427