时间限制:1秒 空间限制:32768K 热度指数:836364
题目描述
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
主要有四种思路
1. 首先是利用栈来进行存储
链接:https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035 来源:牛客网 class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> value; ListNode *p=NULL; p=head; stack<int> stk; while(p!=NULL){ stk.push(p->val); p=p->next; } while(!stk.empty()){ value.push_back(stk.top()); stk.pop(); } return value; } };
2. 数组翻转:数组翻转可以用C++自带的函数,也可以自己实现
class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> value; ListNode *p=NULL; p=head; while(p!=NULL){ value.push_back(p->val); p=p->next; } //reverse(value.begin(),value.end()); //C++自带的翻转函数 int temp=0; int i=0,j=value.size()-1; while(i<j){ temp=value[i]; //也可以用swap函数,swap(value[i],value[j]); value[i]=value[j]; value[j]=temp; i++; j--; } return value; } };
3. 递归想法
class Solution { public: vector<int> value; vector<int> printListFromTailToHead(ListNode* head) { ListNode *p=NULL; p=head; if(p!=NULL){ if(p->next!=NULL){ printListFromTailToHead(p->next); } value.push_back(p->val); } return value; } };
4. 使用反向迭代器
链接:https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035 来源:牛客网 class Solution { public: vector<int> printListFromTailToHead(struct ListNode* head) { vector<int> v; ListNode *p = head; while (p != nullptr) { v.push_back(p->val); p = p->next; } //反向迭代器创建临时对象 return vector<int>(v.rbegin(), v.rend()); } };