一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
1、思路
通常,这种情况下,我们不希望修改原链表的结构。返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,给一个新的链表结构,这样链表就实现了反转。
2、代码
C++:
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 | /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { stack<int> nodes; vector<int> result; ListNode* node = head; while(node != NULL){ nodes.push(node->val); node = node->next; } while(!nodes.empty()){ result.push_back(nodes.top()); nodes.pop(); } return result; } }; |
Python2.7:
对于python来讲,不用如此麻烦,我们可以直接使用列表的插入方法,每次插入数据,只插入在首位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回从尾部到头部的列表值序列,例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here result = [] while listNode: result.insert(0, listNode.val) listNode = listNode.next return result |
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
2018年9月8日 上午9:26 沙发
请问一下大神,c++实现的时候为啥不直接result.push_back(node->val);,这可以少一个stack nodes;的使用
2018年9月8日 上午9:44 1层
@大敏 反转啊,先入先出。直接push_back需要再反转。
2019年2月21日 下午2:14 板凳
不是很理解python中while lisNode 这句为什么能判断真假
2019年2月21日 下午6:43 1层
@Irelia 空就是假了。
2019年2月28日 下午7:22 地板
c++里面你申请的vector并没有用到啊
2019年2月28日 下午10:51 1层
@syq 你再好好看下?
2019年3月1日 上午12:18 2层
@Jack Cui 看错了,不好意思
2019年4月17日 上午10:38 4楼
你这个没把链表的方向反转啊
2019年4月17日 下午2:19 1层
@Dejavu 已经反向了啊,你感觉哪里有问题?
2019年4月17日 下午2:32 2层
@Jack Cui 我的意思是比如1->2->3->4反转应该是4->3->2->1
这道题返回的是向量这种解法可行
但如果要求返回指向head的指针就不对了
2019年4月17日 下午3:54 3层
@Dejavu 按照要求做题,这道题要求返回的,就是列表。你说的是:反转链表,剑指offer有另外一道题。
2019年7月17日 下午5:13 5楼
学习了 膜拜大佬
2019年7月17日 下午7:24 1层
@lanme2019 感谢支持~
2020年10月3日 下午9:38 6楼
博主,你题目打错了吧,返回的应该是一个列表,而不是链表吧?