用递归算法逆置一个带头结点的单链表

用递归算法逆置一个带头结点的单链表涉及到一种常见的“双指针”技巧，但在递归中，我们可以稍微调整思路。首先假设链表的当前节点为`current`，然后递归地对剩余部分（`current->next`）进行逆置，最后再把当前节点的`next`指向上一个节点（即逆置后的`previous`）。这是递归过程的关键：

def reverseList(head):
    # 基线条件：如果链表为空或者只有一个节点，无需逆置，返回头节点
    if head is None or head.next is None:
        return head
    
    # 递归条件：先对后半部分链表进行逆置
    new_head = reverseList(head.next)
    
    # 更新当前节点的next指向前一个节点
    head.next.next = head
    # 把当前节点指向逆置后的链表头
    head.next = None
    
    return new_head

在这个递归过程中，每次函数调用都会把问题规模减小，直到达到基本情况，然后再逐层返回并更新指针。注意递归结束时需要设置`head.next = None`，防止形成环。