面试题5

题目描述:
输入一个链表,从尾到头打印链表每个节点的值。
输入:
每个输入文件仅包含一组测试样例。
每一组测试案例包含多行,每行一个大于0的整数,代表一个链表的节点。第一行是链表第一个节点的值,依次类推。当输入到-1时代表链表输入完毕。-1本身不属于链表。
输出:
对应每个测试案例,以从尾到头的顺序输出链表每个节点的值,每个值占一行。
样例输入:
1
2
3
4
5
-1
样例输出:
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