四種方式實現--從尾到頭輸出鏈表

//三種方式實現--從尾到頭輸出鏈表
#include <stack>
#include <string>
#include <iostream>
usingnamespace std;

class OutFromEnd
{
    public:
        typedef struct node1
        {
            int data;
            node1* next;
            node1(int d):data(d),next(NULL){}
        } node;

        OutFromEnd()
        {
            head=cur=new node(-1);
        }

        void add(int data)
        {
            node* tmp=new node(data);
            cur->next=tmp;
            cur=tmp;
        }

        //借用棧倒序輸出鏈表
        //因為棧是先進后出，把鏈表中的元素存進棧中，鏈表前面的元素在棧底，后面的元素在棧頂，鏈表后面的元素先出棧
void stackMethod()
        {
            if(NULL==head || NULL==head->next)
            {
                return;
            }
 
            node* tmp=head->next;
            stack<int> s;
             
            while(tmp!=NULL)
            {
                s.push(tmp->data);
                tmp=tmp->next;
            }

            while(!s.empty())
            {
                cout<<s.top()<<"\t";
                s.pop();
            }
        }

        /*
            先翻轉鏈表，再按順序打印（主要是想自己實現單鏈表的翻轉，這種實現方式破壞了鏈表的結構，當然再翻轉一下就還原了）
            翻轉鏈表的步驟：
                1:將當前節點的next節點指向他以前的前一個節點
                2:當前節點下移一位
                3:如果是最后一個節點，就把它的next節點指向它以前的前一個節點，并推出循環
        */
        void reverse()
        {
            if(NULL==head || NULL==head->next)
            {
                return;
            }
            cur=head->next;

            node* prev=NULL;
            node* pcur=head->next;
            node* next;
            while(pcur!=NULL)
            {
                if(pcur->next==NULL)
                {
                    pcur->next=prev;
                    break;
                }
                next=pcur->next;
                pcur->next=prev;
                prev=pcur;
                pcur=next;
            }

            head->next=pcur;
             
            node* tmp=head->next;
            while(tmp!=NULL)
            {
                cout<<tmp->data<<"\t";
                tmp=tmp->next;
            }
        }

        void print3()
        {
            recursion(head->next);
        }

        //用遞歸實現
        //很誠實的說盜用了別人的思想，真的太妙了，完全能看出你是否真的體會了遞歸的原理
        //正如那位哥們所說，遞歸就是一個進棧出棧的過程，鏈表前面的元素先進棧，在棧底，后面的元素后進棧，在棧頂，先出棧，哈哈。。。
void recursion(node* head)
        {
            if(NULL==head)
            {
                return;
            }

            if(head->next!=NULL)
            {
                recursion(head->next);
            }

            //如果把這句放在第二個if前面，那就是從頭到尾輸出鏈表，曾經的你或許是用while或者用for循環輸出鏈表，現在你又多了一種方式
            cout<<head->data<<"\t";
        }

        //借用數組實現
void print4()
        {
            node* tmp=head->next;
            int len=0;
            while(tmp!=NULL)
            {
                 ++len;
                tmp=tmp->next;
            }
            tmp=head->next;
            int* A=newint[len] ;
            for(int i=len-1;i>=0;i--)
            {
                A[i]=tmp->data;
                tmp=tmp->next;
            }

            for(int i=0;i<len;i++)
            {
                cout<<A[i]<<"\t";
            }
            delete [] A;
        }


    private :
        node *head,*cur;
};