剑指Offer - 九度1511 - 从尾到头打印链表
2024-08-24 14:30:23
剑指Offer - 九度1511 - 从尾到头打印链表
2013-11-29 21:08
- 题目描述:
-
输入一个链表,从尾到头打印链表每个节点的值。
- 输入:
-
每个输入文件仅包含一组测试样例。
每一组测试案例包含多行,每行一个大于0的整数,代表一个链表的节点。第一行是链表第一个节点的值,依次类推。当输入到-1时代表链表输入完毕。-1本身不属于链表。
- 输出:
-
对应每个测试案例,以从尾到头的顺序输出链表每个节点的值,每个值占一行。
- 样例输入:
-
1
2
3
4
5
-1
- 样例输出:
-
5
4
3
2
1
题意分析:
给定一条单链表,从未到头打印出来。第一个念头是可以用头递归的写法进行倒序输出,但不论头递归还是尾递归都不是个会写代码的人该写出来的,因为递归调用中的栈操作开销太累,而且百万级的数据就能搞出栈溢出了。所以可以采取先反转链表,再输出的方法。至于输出完了要不要再转回去,就看数据还有没有人要用了。不过从原则上来说,既然要求设计的是逆序输出链表,就不应该改变原始数据,应该在处理完了以后把链表给转回来的。本题中的数据时一次性的,我索性输出完了就给释放掉了。
时间复杂度O(n),空间复杂度O(1)。
// 650320 zhuli19901106 1511 Accepted 点击此处查看所有case的执行结果 5088KB 731B 90MS
//
#include <cstdio>
#include <vector>
using namespace std; class ListNode{
public:
int val;
ListNode *next;
ListNode(int _val = ) : val(_val), next(NULL){}
}; int main()
{
ListNode *root;
ListNode *tail;
int n;
vector<ListNode *> vv; root = new ListNode();
tail = root;
vv.clear();
while(scanf("%d", &n) == && n >= ){
tail->next = new ListNode(n);
tail = tail->next;
vv.push_back(tail);
} while(vv.size() > ){
printf("%d\n", vv[vv.size() - ]->val);
vv.pop_back();
} tail = root;
while(tail != NULL){
root = tail->next;
delete tail;
tail = root;
} return ;
}
最新文章
- Unix系统引导过程(简单步骤)
- 手机web——自适应网页设计(html/css控制)
- 引擎崩溃、异常、警告、BUG与提示总结及解决方法
- 黄聪:MySql Host is blocked because of many connection errors; unblock with &#39;mysqladmin flush-hosts&#39; 解决方法(转)
- 函数lock_rec_get_nth_bit
- Dynamics CRM2013 从subgrid中打开快速创建窗体创建数据
- vscode常用插件
- [译]Ocelot - Headers Transformation
- cena评测系统:自定义校验器(自定义评测插件编写)
- 洗礼灵魂,修炼python(59)--爬虫篇—httplib模块
- python接口自动化测试三:代码发送HTTP请求
- cordova 开发笔记
- centos6.8卸载DB2 10.5
- linux下的ping工具--fping
- 再次理解多线程线程安全问题(理解java内存模型后)
- 身份证扫描识别/身份证OCR识别的正确姿势,你get到了吗?
- numpy.random.random &; numpy.ndarray.astype &; numpy.arange
- php 内存泄漏
- Ubuntu 16.04下Shell脚本中使用数组提示:Syntax error: ";("; unexpected
- Repeater绑定List泛型对象