-面试题5:从尾到头打印链表
提交网址: http://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156
本题知识点: 链表
输入一个链表,从尾到头打印链表每个节点的值。
输入描述:
分析:
此题要求返回类型为vector<int>,故有两种方法:
1. 使用vector容器在头部进行插入,模拟堆栈;
2. 使用递归思想实现。
AC代码:
class Solution {
public:
vector<int> printListFromTailToHead(struct ListNode* head) {
vector<int> vec;
ListNode *p;
p=head;
while(p!=NULL)
{
vec.insert(vec.begin(), p->val); // 每次都在向量的开头进行插入
p=p->next;
}
return vec;
}
};
如果想使用stack容器的话,可以这样写:
void printListFromTailToHead(ListNode *head)
{
if(head==NULL) return head;
std::stack <ListNode*> s;
ListNode *p;
while(p!=NULL)
{
s.push(p); // 顶部插入
p=p->next;
}
while(!s.empty())
{
p=s.top(); // 获取到栈顶的结点(指针类型)
cout<<p->val<<" "; // printf("%d\t",p->val);
s.pop(); // pop():出栈,删除栈顶元素
}
}