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

题目描述

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

解题思路

1.辅助栈法
每遍历一个就入栈，然后全pop出来就可以。python可以用arr.reverse()。
2.递归法
每次递归往数组里面加一个val，这样越靠前的越加的晚。

解题代码

辅助栈法：

class Solution:
    def reversePrint(self, head: ListNode) -> list[int]:
        node = head
        stack = []
        while node is not None:
            stack.append(node.val)
            node = node.next
        stack.reverse()
        return stack

递归法：

class Solution:
    def reversePrint(self, head: ListNode) -> list[int]:
        if head is None:
            return []
        node = head
        arr = []
        def dfs(node: ListNode):
            if node.next is not None:
                dfs(node.next)
            arr.append(node.val)
        dfs(head)
        return arr

执行结果

辅助栈法：48ms 16MB
递归法：56ms 26.7MB