典型的后进先出,可以借助栈,也可以使用递归。
考虑到若链表过长递归可能造成函数调用栈溢出,所以使用栈更好。
注意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;
}