JZ-C-16

剑指offer第十六题：反转链表
 1 //============================================================================
 2 // Name        : JZ-C-16.cpp
 3 // Author      : Laughing_Lz
 4 // Version     :
 5 // Copyright   : All Right Reserved
 6 // Description : 反转链表
 7 //============================================================================
 8 
 9 #include <iostream>
10 #include "List.h"
11 #include <stdio.h>
12 using namespace std;
13 
14 ListNode* ReverseList(ListNode* pHead) {
15     ListNode* RevNode = pHead;
16     ListNode* Node = pHead;
17     ListNode* preNode = NULL;
18     while (Node != NULL) {//考虑链表为空的情况
19         ListNode* nexNode = Node->m_pNext;
20         if (nexNode == NULL) {
21             RevNode = Node; //在原链表最后一个结点处，将尾结点赋值为新链表的头结点
22         }
23         Node->m_pNext = preNode; //修改Next结点
24         preNode = Node;
25         Node = nexNode;
26     }
27     return RevNode;
28 }
29 
30 // ====================测试代码====================
31 ListNode* Test(ListNode* pHead) {
32     printf("The original list is: 
");
33     PrintList(pHead);
34 
35     ListNode* pReversedHead = ReverseList(pHead);
36 
37     printf("The reversed list is: 
");
38     PrintList(pReversedHead);
39 
40     return pReversedHead;
41 }
42 
43 // 输入的链表有多个结点
44 void Test1() {
45     ListNode* pNode1 = CreateListNode(1);
46     ListNode* pNode2 = CreateListNode(2);
47     ListNode* pNode3 = CreateListNode(3);
48     ListNode* pNode4 = CreateListNode(4);
49     ListNode* pNode5 = CreateListNode(5);
50 
51     ConnectListNodes(pNode1, pNode2);
52     ConnectListNodes(pNode2, pNode3);
53     ConnectListNodes(pNode3, pNode4);
54     ConnectListNodes(pNode4, pNode5);
55 
56     ListNode* pReversedHead = Test(pNode1);
57 
58     DestroyList(pReversedHead);
59 }
60 
61 // 输入的链表只有一个结点
62 void Test2() {
63     ListNode* pNode1 = CreateListNode(1);
64 
65     ListNode* pReversedHead = Test(pNode1);
66 
67     DestroyList(pReversedHead);
68 }
69 
70 // 输入空链表
71 void Test3() {
72     Test(NULL);
73 }
74 
75 int main(int argc, char** argv) {
76     Test1();
77     Test2();
78     Test3();
79 
80     return 0;
81 }