chatgpt递归的方式来反转链表

递归的方式来反转链表.md

在C++中，可以使用递归的方式来反转链表。具体步骤如下：

1. 定义一个递归函数reverseList，该函数接收一个指向链表头节点的指针head作为参数，并返回反转后的链表头节点的指针。
2. 在递归函数中，首先判断特殊情况，即如果链表为空或只有一个节点，则直接返回head。
3. 否则，递归调用reverseList函数来反转剩余的链表，并将返回的反转后的链表头节点的指针保存在变量newHead中。
4. 将当前节点的下一个节点的next指针指向当前节点，即将当前节点的下一个节点指向当前节点，实现反转。
5. 将当前节点的next指针置空，即将当前节点的下一个节点置空，防止形成环。
6. 返回newHead作为反转后的链表头节点的指针。

下面是使用C++实现的代码：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    // 特殊情况处理
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    // 递归调用反转剩余的链表
    ListNode* newHead = reverseList(head->next);
    
    // 反转当前节点
    head->next->next = head;
    head->next = nullptr;
    
    return newHead;
}

使用示例：

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);

ListNode* newHead = reverseList(head);

while (newHead != nullptr) {
    cout << newHead->val << " ";
    newHead = newHead->next;
}

输出结果为：5 4 3 2 1

希望对你有帮助！