==========================
面试题06. 从尾到头打印链表
==========================

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

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


示例 1：
::

    输入：head = [1,3,2]

    输出：[2,3,1]


限制：
::

    0 <= 链表长度 <= 10000

----------------------------------------------------------

.. tip::

    从尾到头打印节点，符合 ``后进先出`` 的特点:

        - 借助 ``栈`` 结构来实现
        - 通过天然的栈结构 ``递归`` 来实现，链表过长时，可能会导致栈溢出

.. note::

    - 时间复杂度：O(n)
    - 空间复杂度：O(n)，栈或者递归所需

------------------------------------------------------------

**方法一**：递归

.. code:: python

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

    class Solution(object):
        def reversePrint(self, head):
            """
            :type head: ListNode
            :rtype: List[int]
            """
            def recur(node):
                # terminator
                if not node:
                    return
                # drill down
                recur(node.next)

                # process current level
                self.rs.append(node.val)
            self.rs = []
            recur(head)
            return self.rs

-----------------------------------------------

**方法二**：非递归(栈)

.. code:: python

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

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