5
4
3
2
1
第一种思路,直接使用递归。递归从自后向前输出前一项。耗时90ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
struct ListNode{
int m_nKey;
ListNode* m_pNext;
};
void PrintfRever(ListNode *phead){
if (phead != NULL){
if (phead->m_pNext != NULL){
PrintfRever(phead->m_pNext);
}
//cout << phead->m_nKey << endl;
printf("%d\n", phead->m_nKey);
}
}
int main(){
ListNode *head = NULL;
ListNode *p = NULL;
p = new ListNode;
p->m_pNext = NULL;
head = p;
int n;
//while (cin >> n && n != -1){
while (scanf("%d", &n ) != EOF && n != -1 ){
ListNode *q = NULL;
q = new ListNode;
q->m_nKey = n;
q->m_pNext = p->m_pNext;
p->m_pNext = q;
p = p->m_pNext;
}
PrintfRever(head ->m_pNext);
return 0;
}
第二种思路,使用栈,先压入,然后再输出.耗时90ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
struct ListNode{
int m_nKey;
ListNode* m_pNext;
};
void PrintfRever(ListNode *phead){
std::stack< ListNode*> nodes;
ListNode* pNode = phead;
while (pNode != NULL){
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while (!nodes.empty()){
pNode = nodes.top();
//cout << pNode->m_nKey << endl;
printf("%d\n", pNode->m_nKey);
nodes.pop();
}
}
int main(){
ListNode *head = NULL;
ListNode *p = NULL;
p = new ListNode;
p->m_pNext = NULL;
head = p;
int n;
//while (cin >> n && n != -1){
while (scanf("%d", &n ) != EOF && n != -1 ){
ListNode *q = NULL;
q = new ListNode;
q->m_nKey = n;
q->m_pNext = p->m_pNext;
p->m_pNext = q;
p = p->m_pNext;
}
PrintfRever(head ->m_pNext);
return 0;
}
第三种,双向队列,耗时80ms