递归，迭代，堆栈三种方式实现单链表反转（C++）_c++反转链表用栈实现

#include <stack>
using namespace std;
 
struct Node
{
    int val;
    Node *next;
};
 
Node * creat_link()
{
    Node *head=NULL;
    Node *current=NULL;
    Node *tmp=NULL;
    int val=0;
    int num_node=10;
    for(int i=0;i<num_node;i++)
    {
        val=i+1;
        if(i==0)
        {
            current=(Node*)new(Node);
            current->val=val;
            current->next=NULL;
            head=current;
        }
        else
        {
            tmp=(Node*)new(Node);
            tmp->val=val;
            tmp->next=NULL;
            current->next=tmp;
            current=current->next;
 
        }
    }
    return head;
}
 
void show_display_link(Node * head)
{
    Node * current=head;
    while(current!=NULL)
    {
        cout<<current->val<<endl;
        current=current->next;
 
    }
    cout<<"finish!"<<endl;
}
 
Node * reverse_iteration_version(Node * head)
{
    Node * current=NULL;
    Node * next_node=NULL;
    Node * pre=NULL;
    current=head;
    pre=head;
    next_node=current->next;
    current->next=NULL;
    while(next_node!=NULL)
    {
        pre=current;
        current=next_node;
        next_node=next_node->next;
        current->next=pre;
    }
    head=current;
    return head;
}
 
Node * reverse_stack_version(Node * head)
{
    stack <Node * > stack_for_link;
    Node * current,* tmp,*new_head;
    current=head;
    while(current!=NULL)
    {
        stack_for_link.push(current);
        current=current->next;
    }
    current=stack_for_link.top();
    stack_for_link.pop();
    new_head=current;
    while(!stack_for_link.empty())
    {
        tmp=stack_for_link.top();
        stack_for_link.pop();
        cout<<tmp->val<<endl;
        current->next=tmp;
        current=tmp;
    }
    tmp->next=NULL;
    return new_head;
 
}
 
Node * reverse_recursion_version(Node * head)
{
    if(head->next==NULL)
    {
        return head;
    }
    Node *tmp,*new_head;
    tmp=head->next;
    new_head=reverse_recursion_version(tmp);
    tmp->next=head;
    head->next=NULL;
    return new_head;
}
int main()
{
    Node * head=NULL;
    cout << "this is normal order" << endl;
    head=creat_link();
    show_display_link(head);
    cout <<"this is reverse order"<<endl;
    //head=reverse_iteration_version(head);
    //head=reverse_iteration_version(head);
    head=reverse_recursion_version(head);
    show_display_link(head);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123