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操作
- 继续学习吧，太菜了。
