剑指Offer06.从尾到头打印链表

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

。

示例1：

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

限制：

0 <= 链表长度 <= 10000

方法一：辅助栈法

链表只能从前至后访问每个节点，而题目要求倒序输出各节点值，这种先入后出的需求可以借助栈来实现。

算法流程：

1. 入栈：遍历链表，将各节点值push入栈。
2. 出栈：将各个节点值pop出栈，存储于数组并返回。

复杂度分析：

• 时间复杂度O(N)：入栈和出栈共使用O(N)时间。
• 空间复杂度O(N)：辅助栈stack和数组res共使用O(N)的额外空间。

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

复杂度分析

• 时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。
• 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

方法二：递归法

利用递归，先递推至链表末端；回溯时，依次将节点值加入列表，即可实现链表值的倒序输出。

递归解析：

1. 终止条件：当head == None时，代表越过了链表尾节点，则返回空列表；
2. 递推工作：访问下一节点head.next;
3. 回溯阶段：python返回list+当前节点值[head.val];
4. 返回当前list+当前节点值[head.val];

复杂度分析：

• 时间复杂度O(N)：遍历链表，递归N次。
• 空间复杂度O(N)：系统递归需要使用O(N)的栈空间。

class Solution:
	def reversePrint(self, head):
		return self.reversePrint(head.next) + [head.val] if head else []