《剑指offer》面试题16

《剑指offer》面试题16—反转链表

Node* p1 p2 p3

思路：开始时，p1为NULL，p2=phead，p3=p2—>next。使p2—>next = p1，然后使p1=p2，p2=p3。如果只有1个结点则此时p2为NULL，结束循环；否则继续执行，直到p2为NULL。

注意：注意代码鲁棒性！判断头结点为NULL；如果只有一个结点。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 
 5 class Node
 6 {
 7 public:
 8     Node(int v, Node* n)
 9     {val = v;
10     next = n;}
11     ~Node(){}
12     int val;
13     Node* next;
14 };
15 Node * phead = NULL;
16 Node * pReverseHead = NULL;
17 
18 void AddNode(int val)
19 {
20     Node* pnode = new Node(val,NULL);
21     //Node one_node(val,NULL); 这里有大bug！如果这样写，在函数退出时自动调用析构函数！链表就乱了！
22     if(phead == NULL)
23     {
24         phead = pnode;
25     }
26     else
27     {
28         Node* p = phead;
29         while(p->next != NULL)
30         {
31             p = p->next;
32         }
33         p->next = pnode;
34     }
35 }
36 void PrintLink()
37 {
38     Node* p = phead;
39     while(p != NULL)
40     {
41         int temp = p->val;
42         cout<<temp<<endl;
43         p = p->next;
44     }
45 }
46 void PrintLinkReverse()
47 {
48     Node* p = pReverseHead;
49     while(p != NULL)
50     {
51         int temp = p->val;
52         cout<<temp<<endl;
53         p = p->next;
54     }
55 }
56 Node* ReverseLink()
57 {
58     Node* pPrev = NULL;
59     Node* pNode = phead;
60     Node* pNext;
61     if(phead == NULL) return NULL;
62     while(pNode != NULL)
63     {
64         pNext = pNode->next;
65         if(pNext == NULL)
66         {
67             pReverseHead = pNode;
68         }
69 
70         pNode->next = pPrev;
71         pPrev = pNode;
72         pNode = pNext;
73 
74     }
75     return pReverseHead;
76 }
77 int main()
78 {
79     int val;
80     cin>>val;
81     while(val != 0)
82     {
83         AddNode(val);
84         cin>>val;
85     }
86     PrintLink();
87     Node* pReverseHead = ReverseLink();
88     cout<<"Reverse:"<<endl;
89     PrintLinkReverse();
90     return 0;
91 }

View Code