c++语言程序设计算法习题之如何反转链表。链表的定义。

题目来自剑指Offer

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

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

解决与链表相关的问题总是有大量的指针操作，非常容易出错。为了避免出错，最好先进行全面的分析。在实际的软件开发周期中，设计的时间通常不会比编码的时间短。在编码之前仔细分析和设计，将会给面试官留下很好的印象。与其很快写出一段漏洞百出的代码，倒不如仔细分析再写出鲁棒的代码。

为了正确的反转一个链表，需要调整链表中指针的方向。如下图，在调整结点i的m_pNext指针时，需要知道i的前一个结点h，因为需要把结点i的m_pNext指向结点h。同时，还要事先保存i的下一个结点j，以防止链表断开。

链表反转后的头结点，就是原链表的尾结点，也就是m_pNext为NULL的结点。

基于上述分析，不难写出如下代码：ListNode* ReverseList(ListNode* pHead)

c++语言反转链表实例代码

#include <iostream>
#include <assert.h>
using namespace std;

struct LinkNode
{
int m_Data;
struct LinkNode* m_pNext;
};

void ReverseList(LinkNode* pHead)
{
assert(pHead != NULL);
LinkNode* pCurNode = NULL;
LinkNode* pNextNode = NULL;
pCurNode = pHead->m_pNext;
pHead->m_pNext = NULL;
while (pCurNode)
{
pNextNode = pCurNode->m_pNext;

pCurNode->m_pNext = pHead;
pHead = pCurNode;

pCurNode = pNextNode;
}
return pHead;
}

void CreateListBackword(LinkNode*& pHead,int nLen)
{
assert(pHead == NULL && nLen > 0);
LinkNode* pNewNode = NULL;
for (int i = 0;i < nLen;i++)
{
pNewNode = new LinkNode;
cin>>pNewNode->m_Data;
pNewNode->m_pNext = NULL;

if (pHead == NULL)
{
pHead = pNewNode;
}
else
{
pNewNode->m_pNext = pHead;
pHead = pNewNode;
}
}
}
void PrintList(LinkNode* pHead)
{
assert(pHead != NULL);
while (pHead)
{
cout<<pHead->m_Data<<” “;
pHead = pHead->m_pNext;
}
cout<<endl;
}

int main()
{
int nLen = 0;
struct LinkNode* pHead = NULL;
cout<<”please input node num: “;
cin >> nLen;
CreateListBackword(pHead,nLen);
PrintList(pHead);
pHead = ReverseList(pHead);
PrintList(pHead);
system(“pause”);
return 1;
}