剑指Offer之面试题6：从尾到头打印链表

面试题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)$

借助栈

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

class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if not ListNode:
return n
stack = [] # 模拟栈
while head:
stack.append(head.val)
head = head.next
return stack[::-1]

时间复杂度 $O(n)$：n 是链表的长度，遍历整个链表
空间复杂度 $O(n)$：额外存储结点数组空间

反转后打印

如果借助于额外的空间的话，我们借助于一个列表。可以先把原链表遍历一遍，进行反转，反转后再打印输出。

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

cur, pre = head, None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp

res = []
while pre:
res.append(pre.val)
pre = pre.next
return res

时间复杂度 $O(n)$：n 是链表的长度，遍历这个链表
空间复杂度 $O(n)$：额外存储结点数组空间

总结

链表的题目还是很好理解的，也是整个算法中的基础。理解好链表的各种操作才好去理解其他的数据结构与算法思想，如果对链表实现感兴趣，推荐看之前写过的一篇 Python 实现链表的文章，点​​此处​​。

【文章转自日本多IP站群服务器 http://www.558idc.com/japzq.html提供，感恩】