问题：输入一个链表的头结点，从尾到头反过来打印出每个结点。

这道题的一个明显的思路是采用栈在遍历时保存每个结点，然后分别弹出栈的元素打印，由于栈具有FILO特性，以此达到从尾到头打印链表。注意，由于是打印链表（只读），不能修改输入链表的结构。

先实现栈结构

class Stack:

def __init__(self):
        self._s = []

def push(self, item):
        self._s.append(item)

def pop(self):
        return self._s.pop()

def empty(self):
        return len(self._s) == 0

def top(self):
        return self._s[-1]

建立链表。为了测试的方便，这里编写一函数，根据输入的序列，建立以该序列为结点的链表并返回链表的头。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def __repr__(self):
        return "Node<{}>".format(self.value)

def build_linked_list(node_list):
    if not node_list:
        return Node(None)
    root = Node(node_list[0])
    val = root # 当做游标使用
    for value in node_list[1:]:
        node = Node(value)
        val.next = node
        val = node
    return root

实现从尾到头打印链表的函数。

def print_list_reversingly(root):
    stack = Stack()
    p_node = root
    while p_node.next:
        stack.push(p_node.value)
        p_node = p_node.next
    stack.push(p_node.value)

while not stack.empty():
        node = stack.top()
        print("node: {}\t".format(node))
        stack.pop()

该函数入栈部分还可以优化：

def print_list_reversingly(root):
    stack = Stack()
    p_node = root
    while p_node:
        stack.push(p_node.value)
        p_node = p_node.next

while not stack.empty():
        node = stack.top()
        print("node: {}\t".format(node))
        stack.pop()

测试效果：

root = build_linked_list(list("987654321"))
print_list_reversingly(root)

输入结果：

node: 1	
node: 2	
node: 3	
node: 4	
node: 5	
node: 6	
node: 7	
node: 8	
node: 9

这正是我们所期待的。

另外还有一种思路，采用递归，因为递归本质上也是栈结构，知识这个栈的每个元素都是函数的返回结果。这一点，我们可以对比二叉树的前序、中序遍历打印的递归思路。

这里的思路是，每访问一个结点，递归输出它后面的结点。

def print_recursively(root):
    p_node = root
    if p_node:
        if p_node.next:
            print_recursively(p_node.next)
        print(p_node.value) # print(p_node)

这种思路要注意栈溢出，Python默认的递归深度（栈深度）是1000。可以通过sys.setrecursionlimit修改栈的大小。在Python语言下，如果我们想保留输出结构而不是打印，用于其他处理，可以把上述的实现中print()改为yield。