剑指offer笔记@从尾到头打印链表（附Python代码）

本文主要是介绍剑指offer笔记@从尾到头打印链表（附Python代码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

思路1

依次遍历，构建正序列表。再使用list的方法list.reverse()对列表进行翻转。

该方法没有返回值，但是会对列表的元素进行反向排序。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code hereif not listNode:return []result=[]while listNode:result.append(listNode.val)listNode=listNode.nextresult.reverse()return result

运行时间：28ms

占用内存：5868k

思路2

将列表视为栈操作，先进后出。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code hereif listNode is None:return []else:TempList = []LastList = []while listNode is not None:TempList.append(listNode.val)        #入栈listNode = listNode.nextwhile len(TempList) is not 0:LastList += [TempList.pop()]         #出栈return LastList

运行时间：24ms

占用内存：5728k

思路3

递归。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:# 返回从尾部到头部的列表值序列，例如[1,2,3]def printListFromTailToHead(self, listNode):# write code hereif listNode == None:return []# 每次递归都会产生一个[val],但是新产生的列表都在前面进行连接，所以最终结果是逆序的。return(self.printListFromTailToHead(listNode.next) + [listNode.val])

运行时间：24ms

占用内存：5856k