难度: Easy
书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。
示例 1：
输入：head = [3,6,4,1] 输出：[1,4,6,3]
提示：
0 <= 链表长度 <= 10000
Submission
运行时间: 128 ms
内存: 24 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if head is None:
return []
return self.reversePrint(head.next) + [head.val]
Explain
这个题解采用了递归的方法来实现链表的反转打印。它首先检查当前链表节点是否为空，如果是，则返回一个空列表。如果不为空，它会递归地调用自身，传入下一个节点作为参数。在递归返回时，它会将当前节点的值附加到结果列表的末尾，这样，通过递归的返回过程，就自动实现了链表的倒序排列。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if head is None:
return [] # 如果当前节点为空，则返回空列表
return self.reversePrint(head.next) + [head.val] # 递归调用，处理下一个节点，并将当前节点的值加到返回的列表末尾
Explore
是的，递归方法在处理非常长的链表时可能会遇到栈溢出的问题，因为每次递归调用都会占用一定的栈空间。如果链表的长度超出了栈的深度限制，就会发生栈溢出。为了避免这个问题，可以使用迭代方法来代替递归。例如，可以使用栈来手动模拟递归过程，先将所有节点按顺序入栈，然后再依次出栈以达到倒序打印的效果。这样就能有效避免递归导致的栈溢出问题。
递归方法通常更直观和简洁，特别是在需要反向处理数据时，如链表的倒序打印。递归自然地实现了反向遍历，因为它会先到达链表的末端然后在返回过程中逐步处理节点。然而，递归的缺点是它依赖于函数调用栈，可能导致栈溢出问题，尤其是在链表非常长时。相比之下，迭代方法虽然代码可能更复杂一些，但它不会占用额外的栈空间，因此在处理大数据量时更加稳定和安全。
具体实现方式是通过递归调用返回当前节点之后所有节点组成的列表，然后使用列表的连接操作将当前节点的值加到这个列表的末尾。在 Python 中，这通过 `self.reversePrint(head.next) + [head.val]` 实现。这里，`self.reversePrint(head.next)` 返回的是从当前节点的下一个节点到链表末尾的所有节点的值组成的列表，然后通过 `+ [head.val]` 操作将当前节点的值添加到这个列表的末尾。这样，每层递归都在其返回的列表末尾添加当前节点的值，最终形成一个完整的倒序列表。
在递归方法中，如果链表存在循环引用，那么递归将无限进行下去，因为永远也到达不了链表的尾部。为了处理这种情况，需要在遍历链表时添加额外的检测机制来识别循环。一种常见的方法是使用哈希表或快慢指针技术。哈希表可以存储已访问过的节点，如果再次访问到同一个节点，说明存在循环。快慢指针则是使用两个指针以不同的速度移动，如果链表中存在循环，那么这两个指针最终会相遇。在实际的递归实现中，如果检测到循环，应当抛出异常或者终止递归。