剑指offer：从尾到头打印链表 Python | collections.deque模块的使用

链表学习博客

链表：必须从第一个结点开始

但是链表在内存中是不连续，为什么叫链表，就是感觉像是用链子把一个个节点串起来的。那么一个个节点是怎么串接起来的呢，就是指针，每一个节点（末尾节点除外）都包含了指向下一个节点的指针，也就是说指针中保存着下一个节点的首地址，这样，1号节点知道2号节点保存在什么地址，2号节点知道3号节点保存在什么地址…以此类推。就像现实中寻宝一样，你只知道1号藏宝点，所以你先到达1号藏宝点，1号藏宝点你会得到2号藏宝点的地址，然后你再到达2号藏宝点…直到你找到了你需要的宝藏。链表的遍历就是用这种原理。

#coding:utf-8
###1 链表
##1.1 第五题 从尾到头打印链表
##题目：输入一个链表，从尾到头打印链表每个节点的值

#关于链表：
# class ListNode:
#     def __init__(self, x):
#         self.val = x # val表示value
#         self.next = Node # next表示指针

#方法一:将链表中的value遍历到list中，再倒序输出list
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromeTailToHead(self, listNode):
    	if listNode is None:
    		return []
        l = [] #创建空list
        while listNode:
            l.append(listNode.val) #将当前位置上的value加入到list中；
            # 使用insert(0, listNode.val)插入到第0个位置也可以，不需要倒序输出
            listNode = listNode.next #将指针指向下一个结点
        return l[::-1] #倒序输出

            #insert(0, val)的使用
            # l1 = [1,2,3,4,5]
            # l2 = []
            # for i in l1:
            #     l2.insert(0, i)
            # print(l2)
#使用insert
class Solution:
    def printListFromTailToHead(self, listNode):
        if listNode is None:
    		return []
        l = []
        while listNode:
            l.insert(0, listNode.val)
            listNode = listNode.next
        return l
#方法二：使用deque模块
'''
deque的方法：
append：同list中的append
appendleft:同list中的insert(0, value)
a = deque([1,2,3])
b = deque((1,2,3))
print('a = ', a)
print('b = ', b)
#a = deque([1, 2, 3])
#b = deque([1, 2, 3])
'''
from collections import deque #双向队列
class Solution:
    def printListFromTailToHead(self, listNode):
        if listNode is None:
    		return []
        l =deque() #不是list
        while listNode:
            l.appendleft(listNode.val)
            listNode = listNode.next
        return l