目描述
输入一个链表,从尾到头打印链表每个节点的值。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
方法一:
//用栈来实现
/*class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
std::stack<ListNode*> nodes; //用栈来实现,因为栈是"后进先出".
ListNode* pNode=head;
vector<int> vec;
while(pNode!=NULL)
{
nodes.push(pNode);
pNode=pNode->next;
}
while(!nodes.empty())
{
pNode=nodes.top(); //返回栈顶的元素,但不删除该元素
//vec[i]=pNode->val; 容器不能这样赋值
vec.push_back(pNode->val);
nodes.pop(); //删除栈顶元素,但不返回其值
}
return vec;
}
};*/
方法2:
//利用递归来实现 递归在本质上就是一个栈结构,于是很自然地想到了用递归实现
class Solution { //要实现反过来输出链表,我们每访问到一个结点的时候,先递归输出它后面的结点,再输出该结点本身,这样链表的输出结果就反过来了
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> vec;
if(head!=NULL)
{
if(head->next!=NULL)
{
vec=printListFromTailToHead(head->next); // 这里一定要用vec=,不然递归时没有上一层的值,最终vec只会输出一个值
}
vec.push_back(head->val);
}
return vec;
}
};