四种方式实现倒序输出

　　方法一：借用栈倒序输出链表

　　方法二：先翻转链表，再顺序输出

　　方法三：递归实现，好方法

　　方法四：用数组实现

　　方法一：借用栈倒序输出链表

　　因为栈是先进后出，把链表中的元素存进栈中，链表前面的元素在栈底，后面的元素在栈顶，链表后面的元素先出栈

　　方法二：先翻转链表，再按顺序打印（主要是想自己实现单链表的翻转，这种实现方式破坏了链表的结构，当然再翻转一下就还原了）

　　翻转链表的步骤：

　　1:将当前节点的next节点指向他以前的前一个节点

　　2:当前节点下移一位

　　3:如果是最后一个节点，就把它的next节点指向它以前的前一个节点，并推出循环

　　方法三：用递归实现

　　很诚实的说盗用了别人的思想，真的太妙了，完全能看出你是否真的体会了递归的原理

　　正如那位哥们所说，递归就是一个进栈出栈的过程，链表前面的元素先进栈，在栈底，后面的元素后进栈，在栈顶，先出栈，哈哈。

　　方法四：借用数组实现

　　跟用栈实现的方式差不多，空间复杂度都是O(n)。

1 　　#include 
     
        2   3 　　#include 
      
         4   5 　　#include 
       
          6   7 　　using namespace std;  8   9 　　class OutFromEnd 10  11 　　{ 12  13 　　public: 14  15 　　typedef struct node1 16  17 　　{ 18  19 　　    int data; 20  21 　　    node1* next; 22  23 　　    node1(int d):data(d),next(NULL){} 24  25 　　} node; 26  27 　　OutFromEnd() 28  29 　　{ 30  31 　　    head=cur=new node(-1); 32  33 　　} 34  35 　　void add(int data) 36  37 　　{ 38  39 　　    node* tmp=new node(data); 40  41 　　    cur->next=tmp; 42   43 　　    cur=tmp; 44  45 　　} 46  47 　　//借用栈倒序输出链表 48  49 　　//因为栈是先进后出，把链表中的元素存进栈中，链表前面的元素在栈底，后面的元素在栈顶，链表后面的元素先出栈 50  51 　　void stackMethod() 52  53 　　{ 54  55 　　    if(NULL==head || NULL==head->next) 56  57 　　    { 58  59 　　        return; 60  61 　　    } 62  63 　　    node* tmp=head->next; 64  65 　　    stack
        
          s; 66   67 　　    while(tmp!=NULL) 68  69 　　    { 70  71 　　        s.push(tmp->data); 72  73 　　        tmp=tmp->next; 74  75 　　    } 76  77 　　    while(!s.empty()) 78  79 　　    { 80  81 　　        cout<
         
          <<"\t"; 82  83 　　        s.pop(); 84  85 　　    } 86  87 　　} 88  89 　　 90  91 　　void reverse() 92  93 　　{ 94  95 　　    if(NULL==head || NULL==head->next) 96  97 　　    { 98  99 　　        return;100 101 　　    }102 103 　　    cur=head->next;104 105 　　    node* prev=NULL;106 107 　　    node* pcur=head->next;108 109 　　    node* next;110 111 　　    while(pcur!=NULL)112 113 　　    {114 115 　        　if(pcur->next==NULL)116 117 　　        {118 119 　　            pcur->next=prev;120 121 　　            break;122 123 　　        }124 125 　　        next=pcur->next;126 127 　　        pcur->next=prev;128 129 　　        prev=pcur;130 131 　　        pcur=next;132 133 　　    }134 135 　　    head->next=pcur;136 137 　　    node* tmp=head->next;138 139 　　    while(tmp!=NULL)140 141 　　    {142 143 　　        cout<
          
           data<<"\t";144 145 　　 tmp=tmp->next;146 147 　　 }148 149 　　}150 151 　　void print3()152 153 　　{154 155 　　 recursion(head->next);156 157 　　}158 159 　　//用递归实现160 161 　　//很诚实的说盗用了别人的思想，真的太妙了，完全能看出你是否真的体会了递归的原理162 163 　　//正如那位哥们所说，递归就是一个进栈出栈的过程，链表前面的元素先进栈，在栈底，后面的元素后进栈，在栈顶，先出栈，哈哈。。。164 165 　　void recursion(node* head)166 167 　　{168 169 　　 if(NULL==head)170 171 　　 {172 173 　　 return;174 175 　　 }176 177 　　 if(head->next!=NULL)178 179 　　 {180 181 　　 recursion(head->next);182 183 　 　}184 185 　　//如果把这句放在第二个if前面，那就是从头到尾输出链表，曾经的你或许是用while或者用for循环输出链表，现在你又多了一种方式186 187 　　 cout<
           
            data<<"\t";188 189 　　}190 191 　　//借用数组实现192 193 　　void print4()194 195 　　{196 197 　　 node* tmp=head->next;198 199 　　 int len=0;200 201 　　 while(tmp!=NULL)202 203 　　 {204 205 　　 ++len;206 207 　　 tmp=tmp->next;208 209 　　 }210 211 　　 tmp=head->next;212 213 　　 int* A=new int[len] ;214 215 　　 for(int i=len-1;i>=0;i--)216 217 　　 {218 219 　　 A[i]=tmp->data;220 221 　　 tmp=tmp->next;222 223 　　 }224 225 　　 for(int i=0;i