题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
法一：递归
include <iostream>
include <vector>
using namespace std;
struct ListNode
{
public:
int val;
struct ListNode *next;
/*ListNode(int x) :
val(x), next(NULL)
{
}*/
};
class Solution
{
private:
vector<int> res;
public:
vector<int> printListFromTailToHead(ListNode *head)
{
Recurse(head);
return res;
}
void Recurse(ListNode *head)
{
if (head)
{
Recurse(head->next);
res.push_back(head->val);
}
}
};
int main()
{
ListNode list[4];
list[0].val = 1;
list[0].next = &list[1];
list[1].val = 2;
list[1].next = &list[2];
list[2].val = 3;
list[2].next = &list[3];
list[3].val = 4;
list[3].next = NULL;
Solution solu;
vector<int> res = solu.printListFromTailToHead(list);
cout << "there are " << res.size() << "datas in vector" << endl;
for (int i = 0; i < res.size(); i++)
{
cout << res[i] << endl;
}
cout << system("pause");
return 0;
}
法二：利用栈“后进先出”的思路实现
include <iostream>
include <vector>
include <stack>
using namespace std;
struct ListNode
{
public:
int val;
struct ListNode *next;
/*ListNode(int x) :
val(x), next(NULL)
{
}*/
};
class Solution
{
private:
vector<int> res;
public:
vector<int> printListFromTailToHead(ListNode head)
{
stack<int> st;
ListNode cur = head;
while (cur)
{
st.push(cur->val);
cur = cur->next;
}
while(!st.empty())
{
res.push_back(st.top());
st.pop();
}
return res;
}
};
int main()
{
ListNode list[4];
list[0].val = 1;
list[0].next = &list[1];
list[1].val = 2;
list[1].next = &list[2];
list[2].val = 3;
list[2].next = &list[3];
list[3].val = 4;
list[3].next = NULL;
Solution solu;
vector<int> res = solu.printListFromTailToHead(list);
cout << "there are " << res.size() << "datas in vector" << endl;
for (int i = 0; i < res.size(); i++)
{
cout << res[i] << endl;
}
cout << system("pause");
return 0;
}
牛客网在线检验：替换空格_牛客网
