一、前言
本系列文章为《剑指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 |
更多内容请访问:IT源点
注意:本文归作者所有,未经作者允许,不得转载