python递归实现链表快速倒转

在 Python 中，可以使用递归算法实现链表快速倒转。具体步骤如下：

1. 定义一个递归函数 reverseLinkedList，该函数接受一个链表头节点作为参数。
2. 在函数体内，首先判断当前链表是否只有一个节点或者为空。如果是，直接返回该节点或者 None。
3. 如果当前链表不是一个节点，递归调用 reverseLinkedList 函数并传入链表的下一个节点作为参数，得到返回的结果 new_head。
4. 将当前节点的下一个节点的 next 属性指向当前节点，即将链表反向。然后将当前节点的 next 属性设置为 None，以防止链表循环。
5. 返回 new_head。

下面是 Python 代码示例：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseLinkedList(head):
    # 判断链表为空或者只有一个节点
    if not head or not head.next:
        return head
    # 递归调用
    new_head = reverseLinkedList(head.next)
    # 反转链表
    head.next.next = head
    head.next = None
    # 返回新的头节点
    return new_head

下面是使用示例：

# 创建链表 1 -> 2 -> 3 -> 4
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

# 反转链表
new_head = reverseLinkedList(head)

# 打印反转后的链表 4 -> 3 -> 2 -> 1
while new_head:
    print(new_head.val)
    new_head = new_head.next

输出结果为：

4
3
2
1

再看一个使用示例：

# 创建链表 5 -> 6 -> 7 -> 8 -> 9
head = ListNode(5)
head.next = ListNode(6)
head.next.next = ListNode(7)
head.next.next.next = ListNode(8)
head.next.next.next.next = ListNode(9)

# 反转链表
new_head = reverseLinkedList(head)

# 打印反转后的链表 9 -> 8 -> 7 -> 6 -> 5
while new_head:
    print(new_head.val)
    new_head = new_head.next

输出结果为：

9
8
7
6
5

通过这两个示例，我们可以看到不同的链表经过递归算法后都可以得到正确的倒转结果。需要注意的一点是，在实际应用中，需要注意递归深度，以防止递归栈溢出。