# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
    def recursion(self, head: ListNode, next_node: ListNode):
        is_last = next_node.next is None
        if not is_last:
            last = self.recursion(next_node, next_node.next)
        else:
            last = next_node
        next_node.next = head
        return last

    def ReverseList(self, head: ListNode) -> ListNode:
        # write code here
        if head is None or head.next is None:
            return head
        new_head =  self.recursion(head, head.next)
        head.next = None
        return new_head

初始思路

拿过题目，第一个思路是用一个列表保存全部的链表，然后反转。但题目里要求空间复杂度为 O(1)，作罢

递归

既然如此，只能进行 in-place 原地修改了。使用递归算法：先递归到最深处，然后逐次修改 .next属性，next_node.next = head是关键。

需要注意两点：

• 最后要返回新的 head，所以要返回递归最深处的 next_node，然后逐层传递回第一次对 recursion 的调用
• 递归完成后，需要把原来的 head.next 修改为 None