剑指Offer反转链表

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

1 struct ListNode
2 {
3     int nKey;
4     ListNode *pNext;
5 };

思路：需要三个指针pPre, pCur, pNext，分别前一结点，当前结点以及下一结点，为了防止在反转链表过程中发生链表断裂，需要记录当前结点的下一结点。每一步操作为：

　　1.记录pNext = pCur->pNext； 2. pCur的pNext指向pPre； 3. pPre指向pCur，pCur指向pNext。

此题最容易错误的是发生链表断裂！

code:

 1 //反转链表
 2 ListNode* ReverseList(ListNode *pHead)
 3 {
 4     ListNode *pPre = NULL;
 5     ListNode *pCur = pHead;
 6     ListNode *pNext = NULL;
 7     //记录反转后的头部
 8     ListNode *pReverseHead = NULL;    
 9 
10     while(pCur != NULL)
11     {
12         pNext = pCur->pNext;
13         //pNext为空时的pCur即为反转后的头部
14         if(pNext == NULL)
15             pReverseHead = pCur;
16         pCur->pNext = pPre;
17         pPre = pCur;
18         pCur = pNext;
19     }
20     return pReverseHead;
21 }

example:

备注：容易出错之处：开始想的时候利用pNext != NULL时，来反转链表，当pNext == NULL时，返回pCur即为反转后的头部。(大家知道错在哪里吗？)

ans：上面的思路，错就错在最后一个pCur->pNext并没有指向pPre ；pCur成为一个孤家寡人了，也就是链表断裂。所以，pNext不宜作为while中循环条件，用pCur作为while中的循环条件会好些。不知道有多少人曾经会有这样的想法呢？

下面再给出反转链表的递归版本

 1 ListNode *ReverseListRecursive(ListNode *pHead)
 2 {
 3     if (pHead == NULL || pHead->m_pNext == NULL)
 4     {
 5         return pHead;
 6     }
 7     ListNode *ReverseHead = ReverseListRecursive(pHead->m_pNext);
 8     pHead->m_pNext->m_pNext = pHead;//把后一节点的next指向head
 9     pHead->m_pNext = NULL;    
10     return ReverseHead;
11 }