单链表倒置（递归与非递归）

 1 #include <iostream>
 2 using namespace std;
 3 
 4 #include <stdio.h>
 5 
 6 struct Node {
 7     int data;
 8     Node * next;
 9 };
10 // 非递归
11 Node * Reverse(Node * first)
12 {
13     Node *p = first, *q, *r;
14     if (p == NULL)
15         return p;
16     r = p->next;
17     p->next = NULL;
18     while (r != NULL) {
19         q = r;
20         r = r->next;
21         q->next = p;
22         p = q;
23     }
24     
25     return q;    
26 }
27 
28 // 递归
29 Node * Reverse2(Node * first)
30 {
31     if (first == NULL || first->next == NULL)
32         return first;
33     Node * p = Reverse2(first->next);
34     first->next->next = first;
35     first->next = NULL;
36     return p;
37 }
38 
39 Node * Construct()
40 {
41     Node * node = NULL, *first;
42     int n;
43     scanf("%d", &n);
44     if (n == 0)
45         return NULL;
46     
47     node = new Node;
48     node->data = n;
49     node->next = NULL;
50     first = node;
51     
52     while (scanf("%d", &n) && n != 0) {
53         node->next = new Node;
54         node->next->data = n;
55         node->next->next = NULL;
56         node = node->next;
57     }
58     
59     return first;
60 }
61 
62 void Print(Node * first)
63 {
64     while (first != NULL) {
65         printf("%3d", first->data);
66         first = first->next;
67     }
68     printf("\n");
69 }
70 
71 int main()
72 {
73     Node * first = Construct();
74     Print(first);
75     Print(first = Reverse(first));
76     Print(first = Reverse2(first));
77     Print(first = Reverse2(first));
78     Print(first = Reverse2(first));
79     return 0;
80 }