剑指 Offer 06：从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

我的题解是这样的：

• 先初始化一个空列表
• 如果头节点不存在，直接返回空列表
• 如果头节点存在，通过while循环不断在列表中添加链表节点元素值，循环的条件是head.next为真，每次添加完链表节点值之后，将head变更，保证循环条件是改变的。
• 最后一个元素没有下一个元素，因此head.next为假，不能进入循环，于是在循环外添加节点值
• 使用list的reverse()函数翻转列表，我们需要先verse_list.reverse()，再return verse_list，因为reverse()没有返回值，他的作用是使自生该翻转。千万不能return verse_list.reverse()，这样的结果是None

**ps：注意，for循环中循环变量是自增的，while循环需要自己更新循环条件。 **

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        verse_list = list()
        if not head:
            return verse_list
        else:
            while(head.next):
                verse_list.append(head.val)
                head = head.next
            verse_list.append(head.val)
        # 错误方式，因为list的reverse方法没有返回值
        # return verse_list.reverse() 
            verse_list.reverse()
        return verse_list 

看两个更为优美的答案：
1、递归法

• 将链表从头节点依次向后寻找下一个节点，直到找到最后一个节点，最后一个节点的next是None，返回空列表[ ]
• 遍历到最后一个节点，返回[ ]，之后，函数开始回溯，如果是节点，就将head.val添加进[ ]中

• 直到回溯到第一个元素为止，递归结束。
  我们可以看下面这幅图：

  
  
  递归＋回溯的过程

这个例子充分说明了递归本质上就是一个栈：先进后出

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        return self.reversePrint(head.next) + [head.val] if head else []

2、辅助栈
这个做法和我自己的做法很像，只是变更了while的条件，也因此省去了添加最后一个节点值的麻烦，也不用判断第一个节点是否存在。返回也直接利用stack[::-1]获得翻转值。

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        return stack[::-1]