用递归方法逆置带头节点的单链表

递归方法反转带头节点的单链表是一种常见的算法问题，通常涉及两个关键步骤：

1. **基本情况**：当链表只有一个元素（即头结点没有下一个节点）时，这个链表已经达到了其反转后的状态，直接返回当前节点作为新的头结点。

2. **递归步骤**：对于包含多个元素的链表，我们需要将剩余部分（即头结点的下一个节点及其后续节点）反转，然后再将当前节点链接到反转后的链表头部。这一步通过创建一个新的链表头、递归地反转剩下的链表，然后将原头节点的next指针指向新头节点来完成。

以下是 Python 的递归实现示例：

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

def reverseList(head):
    if not head or not head.next:  # 基本情况
        return head
    else:  # 递归步骤
        new_head = reverseList(head.next)  # 反转剩余部分
        head.next.next = head  # 将原头接到反转后的链表尾部
        head.next = None  # 更新原头的next指针
        return new_head  # 返回新头节点