/*58.从尾到头输出链表（链表）。题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：struct ListNode{int  m_nKey;ListNode* m_pNext;};*/#include <stdio.h>#include <stdlib.h>typedef struct ListNode{int  m_nKey;ListNode* m_pNext;}ListNode;void addNode(ListNode * &pHead, int data){    ListNode * x;    x = pHead;    while(x != NULL && x->m_pNext != NULL)    {        x = x->m_pNext;    }    if(x == NULL)    {        pHead = (ListNode *)malloc(sizeof(ListNode));        pHead->m_nKey = data;        pHead->m_pNext = NULL;    }    else    {        x->m_pNext = (ListNode *)malloc(sizeof(ListNode));        x->m_pNext->m_nKey = data;        x->m_pNext->m_pNext = NULL;    }}void printformback(ListNode * pHead){    int * store = (int *)malloc(100 * sizeof(int)); //对输入的链表长度有限制    int num = 0;    ListNode * x = pHead;    while(x != NULL)    {        store[num++] = x->m_nKey;        x = x->m_pNext;    }    for(int i = num - 1; i >= 0; i--)    {        printf("%d ", store[i]);    }    printf("\n");    free(store);}int main(){    ListNode * a = NULL;    addNode(a, 1);    addNode(a, 2);    addNode(a, 3);    addNode(a, 4);    addNode(a, 5);    addNode(a, 6);    addNode(a, 7);    printformback(a);    return 0;}

//三种方式实现--从尾到头输出链表#include <stack>using namespace 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";        }    private :        node *head,*cur;};