【剑指offer】-从尾到头打印链表-03/67

1. 题目描述:

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

2. 题目分析

2.1 相似题型

  1. 一般的思维来讲,该题直接建立链表,然后在建立链表的时候,直接建立的是反转的链表,题型链接如下:
    数据结构实验之链表二:逆序建立链表
  2. 该题的要求是返回一个ArrayList(数组),不能简单的使用输入输出实现

2.2 c++栈的用法

  1. push(x) – 压一个数到栈顶
  2. pop() – 移除栈顶的元素,不返回任何对象
  3. top() – 返回栈顶端的元素
  4. getMin() – 检索栈中的最小值

2.3 本题做法

  1. 建立一个vector类型的数组(result)
  2. 建立一个栈(stack-arr),用来做链表和数组之间的传递
  3. 遍历链表,将链表中的数值依次使用push来依次压到栈顶
    类型如下:
    1
    2
    链表数值:1 2 3 4 5
    压完的栈:5 4 3 2 1 (先进后出)
  4. 将栈里面的数值依次取出(利用push取出栈顶元素,push_back插入到数组尾部),存入result数组当中,返回该数组

3. 题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 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

数据结构实验之链表二:逆序建立链表【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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. 总结

  1. 学校中的ACM训练题目和这种题目相差较大,在学校中基本没有用过C++中的一些函数,比如上面的一些关于栈的用法。所以,学习的路还有很长。
  2. 关于vector的相关资料——vector详解——vector操作
  3. 继续学习吧,太菜了。
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信