【剑指offer】面试题16、反转链表

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表结点定义如下：
typedef struct Node
{
    int m_nKey;
    struct Node Node *m_pNext;
}ListNode, *pListNode;

分析：

为了正确地反转链表，需要调整链表中指针的方向。为了叙述方便以及更加直观地把过程叙述清楚，我们可以借助图形来直观地分析。在下图（a）所示的链表中，h、i 和 j 是 3 个相邻的结点。假设经过若干操作，我们已经把结点 h 之前的指针调整完毕，这些结点的 m_pNext 都指向各自的前面一个结点。接下来我们把 i 的 m_pNext 指向 h，此时的链表结构如图（b）所示：

由于结点 i 的 m_pNext 指向了结点 h，这样链表就断开了，导致我们找不到结点 j，为了避免链表在结点 i 处断开，我们需要在调整结点 i 的 m_pnext 之前，把结点 j 保存下来。

除此之外，我们还需要保存结点 h，因为我们需要把结点 i 的 m_pnext 指向结点 h。

综上所述，我们需要定义 3 个指针pPre、pNode、pNext分别保存结点 h，结点 i 和结点 j。

最后我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾结点。哪个结点时尾结点？自然是 m_pnext 为 NULL 的结点。

在代码中应主义以下 3 种问题：

1 输入的链表头指针为 NULL 或者整个链表只有一个结点时，程序立即崩溃；
2 反转后的链表出现断裂。
3 返回的反转后的头结点不是原始链表的尾结点。

完整的代码如下：

 1 // reverseList.c
 2 #include "stdio.h"
 3 #include "stdlib.h"
 4 #include "time.h"
 5 
 6 #define N 10
 7 
 8 typedef struct Node
 9 {
10     int m_nValue;
11     struct Node *m_pNext;
12 }ListNode, *pListNode;
13 
14 void createList(ListNode **pHead, int len)
15 {
16     ListNode *pTail = NULL;
17 
18     while(len--)
19     {
20         ListNode *pNew = (ListNode*)malloc(sizeof(ListNode));
21         pNew->m_nValue = rand()%100;
22         pNew->m_pNext = NULL;
23 
24         if(*pHead == NULL)
25         {
26             *pHead = pNew;
27             pTail = pNew;
28         }
29         else
30         {
31             pTail->m_pNext = pNew;
32             pTail = pNew;
33         }
34     }
35 }
36 
37 void printList(ListNode *pHead)
38 {
39     while(pHead != NULL)
40     {
41         printf("%3d ", pHead->m_nValue);
42         pHead = pHead->m_pNext;
43     }
44     printf("
");
45 }
46 
47 ListNode *reverseList(ListNode *pHead)
48 {
49     ListNode *pReverseHead = NULL;
50     ListNode *pNode = pHead;
51     ListNode *pPre = NULL;
52 
53     while(pNode != NULL)
54     {
55         ListNode *pNext = pNode->m_pNext;
56 
57         if(pNext == NULL) // 此时pNode为原始链表的尾结点
58             pReverseHead = pNode;
59         // 连接结点
60         pNode->m_pNext = pPre; 
61         // 向后移动
62         pPre = pNode; 
63         pNode = pNext;
64     }
65     return pReverseHead;
66 }
67 
68 int main(int argc, char const *argv[])
69 {
70     srand(time(NULL));
71 
72     ListNode *pHead = NULL;
73 
74     createList(&pHead, N);
75     printf("Before: ");
76     printList(pHead);
77 
78     ListNode *pReverseHead = reverseList(pHead);
79     if(pReverseHead != NULL)
80     {
81         printf("The pReverseHead Node: %d
", pReverseHead->m_nValue);
82     }
83     printf("After: ");
84     printList(pReverseHead);
85 
86     return 0;
87 }

View Code

本文完。