面试题：从尾到头打印链表

题目：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

方法1：使用栈

/*
链表节点定义如下：
struct ListNode
{
	int _data;
	ListNode* _next;
};
*/


void PrintListTailToHead(ListNode* phead)
{
	assert(phead);

	stack<ListNode*> s;
	ListNode* cur = phead;
	while (cur)
	{
		s.push(cur);
		cur = cur->_next;
	}

	while (!s.empty())
	{
		cout<<s.top()->_data<<" ";
		s.pop();
	}
	cout<<endl;
}

方法2：递归

void PrintListTailToHead(ListNode* phead)
{
	if (phead == NULL)
	{
		return;
	}

	PrintListTailToHead(phead->_next);

	cout<<phead->_data<<" ";
}