用C++单链表就地逆置算法

在C++中，单链表的就地逆置（也称为原地逆置或反转）是指在不使用额外空间的情况下，改变链表节点的指向，使得原来的头结点变成新的尾节点，而原来的尾节点变成新的头节点。以下是常见的递归和迭代两种方式的算法：

**1. 递归法**

void reverseList(Node* &head) {
    if (head == nullptr || head->next == nullptr) { // base case: 空链表或只有一个元素的链表
        return;
    }
    Node *prev = nullptr; // 上一个节点
    Node *curr = head; // 当前节点
    reverseList(curr->next); // 递归处理剩余部分
    prev = curr; // 更新prev为当前节点
    curr->next = prev; // 交换 curr 和 prev 的指针
    head = curr; // 新的头节点是当前节点
}

**2. 迭代法**

void reverseList(Node* &head) {
    Node *prev = nullptr, *curr = head, *next = nullptr;
    while (curr != nullptr) {
        next = curr->next; // 记录当前节点的下一个节点
        curr->next = prev; // 将当前节点的next指向前一个节点
        prev = curr; // 移动prev到curr
        curr = next; // 移动curr到下一个节点
    }
    head = prev; // 最终的新头节点是原始的尾节点
}