问题：输入一个链表的头结点，从尾到头反过来打印出每个结点。
原理：
这道题的一个明显的思路是采用栈在遍历时保存每个结点，然后分别弹出栈的元素打印，由于栈具有FILO特性，以此达到从尾到头打印链表。注意，由于是打印链表（只读），不能修改输入链表的结构。
实现：
先实现栈结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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]
|
建立链表。为了测试的方便，这里编写一函数，根据输入的序列，建立以该序列为结点的链表并返回链表的头。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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
|
实现从尾到头打印链表的函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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()
|
该函数入栈部分还可以优化：
1
2
3
4
5
6
7
8
9
10
11
| 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()
|
测试效果：
1
2
| root = build_linked_list(list("987654321"))
print_list_reversingly(root)
|
输入结果：
1
2
3
4
5
6
7
8
9
| node: 1
node: 2
node: 3
node: 4
node: 5
node: 6
node: 7
node: 8
node: 9
|
这正是我们所期待的。
另外还有一种思路，采用递归，因为递归本质上也是栈结构，知识这个栈的每个元素都是函数的返回结果。这一点，我们可以对比二叉树的前序、中序遍历打印的递归思路。
这里的思路是，每访问一个结点，递归输出它后面的结点。
1
2
3
4
5
6
| def print_recursively(root):
p_node = root
if p_node:
if p_node.next:
print_recursively(p_node.next)
print(p_node.value)
|
这种思路要注意栈溢出，Python默认的递归深度（栈深度）是1000。可以通过sys.setrecursionlimit修改栈的大小。在Python语言下，如果我们想保留输出结构而不是打印，用于其他处理，可以把上述的实现中print()改为yield。
完。
