1. 题目描述:
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
2. 题目分析
2.1 相似题型
- 一般的思维来讲,该题直接建立链表,然后在建立链表的时候,直接建立的是反转的链表,题型链接如下:
数据结构实验之链表二:逆序建立链表 - 该题的要求是返回一个ArrayList(数组),不能简单的使用输入输出实现
2.2 c++栈的用法
- push(x) – 压一个数到栈顶
- pop() – 移除栈顶的元素,不返回任何对象
- top() – 返回栈顶端的元素
- getMin() – 检索栈中的最小值
2.3 本题做法
- 建立一个vector类型的数组(result)
- 建立一个栈(stack-arr),用来做链表和数组之间的传递
- 遍历链表,将链表中的数值依次使用push来依次压到栈顶
类型如下:
链表数值:1 2 3 4 5
压完的栈:5 4 3 2 1 (先进后出)
- 将栈里面的数值依次取出(利用push取出栈顶元素,push_back插入到数组尾部),存入result数组当中,返回该数组
3. 题目代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head)
{
vector <int> result;
stack <int> arr;
ListNode *p = head;
int sum = 0;
while(p != NULL)
{
arr.push(p->val);
p = p->next;
}
int len = arr.size();
int num;
for(int i = 1; i <= len; i++)
{
result.push_back(arr.top());
arr.pop();
}
return result;
}
};
//运行时间:2ms
//占用内存:592k
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *next;
};
int main()
{
struct node *p, *head;
head = (struct node *)malloc(sizeof(struct node));
head->next = NULL;
int n;
cin>>n;
for(int i = 1; i <= n; i++)
{
p = (struct node *)malloc(sizeof(struct node));
cin>>p->data;
p->next = head->next;
head->next = p;
}
for(p = head->next; p != NULL; p = p->next)
{
if(p->next == NULL)
{
cout<<p->data<<endl;
}
else
{
cout<<p->data<<" ";
}
}
return 0;
}
4. 总结
- 学校中的ACM训练题目和这种题目相差较大,在学校中基本没有用过C++中的一些函数,比如上面的一些关于栈的用法。所以,学习的路还有很长。
- 关于vector的相关资料——vector详解——vector操作
- 继续学习吧,太菜了。