[剑指Offer]6-从尾到头打印链表

典型的后进先出，可以借助栈，也可以使用递归。

考虑到若链表过长递归可能造成函数调用栈溢出，所以使用栈更好。

注意stack无遍历操作，全部用push(),pop(),top()完成。

以下创建列表胡乱写例子，主要练习链表倒序输出功能。

#include <iostream>

#include <stack>

using namespace std;

typedef struct List{

    int value;

    List *pNext;

    List(){

        value=0;

        pNext=NULL;

    }

}List;

List* createListTest(){

    List *pHead;

    List *pNode1=new List();

    List *pNode2=new List();

    pNode1->value=1;

    pNode1->pNext=pNode2;

    pNode2->value=2;

    pNode2->pNext=NULL;

    pHead=pNode1;

    pNode1=NULL;

    return pHead;

}

//倒序打印链表

void printListReverse(List *pHead){

    stack<int> s;

    if(pHead==NULL){

        return;

    }

    List *p=pHead;

    while(p){

        s.push(p->value);

        p=p->pNext;

    }

    while(!s.empty()){

        int value=s.top();

        cout<<value<<endl;

        s.pop();

    }

}

int main() {

    List *pTest1=createListTest();

    List *pTest2=NULL;

    printListReverse(pTest1);

    //printListReverse(pTest2);

    cout<<"finish!"<<endl;

    return 0;

}