如何实现从尾到头逆序打印单链表？

本文共计716个文字，预计阅读时间需要3分钟。

题目6：从尾到头打印链表输入：链表的头节点输出：从尾到头返回每个节点的值（用数组返回）示例：输入：head=[1,3,2] 输出：[2,3,1]限制：0 ≤ 链表长度 ≤ 10000思路：考查链表

面试题6: 从尾到头打印链表

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

示例 1：

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

输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

思路

考察链表的基本操作，需要对做题者对链表的基本操作熟悉。

递归方法

利用递归也可以实现链表倒着输出，即每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的结果就反过来了。

class Solution:
def reversePrint(self, head: ListNode) -> List[int]:

if not head:
return []

return self.reversePrint(head.next) + [head.val]

此种方法时间复杂度：$O(n)$，空间复杂度: $O(n)$

借助栈

借助于栈的先进后出的特点。先从头到尾遍历链表，然后把遍历的结果放入栈中（先进后出），最后输出栈，这样利用栈就实现了从尾到头输出链表元素。