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

在C++中，你可以使用递归的方法来逆置一个带头节点的单链表。递归的关键在于将复杂的问题分解成更小的子问题，并且每次解决完子问题后将结果链接起来。这里是一个基本的思路：

// 假设头节点为ListNode，包含数据域data和指向下一个节点的指针next
struct ListNode {
    int data;
    ListNode* next;
};

ListNode* reverseList(ListNode* head) {
    // 如果链表为空或者只有一个元素，无需反转，直接返回头节点
    if (!head || !head->next) {
        return head;
    }

    // 递归步骤：创建一个新的头节点，它将成为原链表第一个节点的前驱
    ListNode* newHead = new ListNode(head->data);
    // 递归处理剩余部分，并连接新的头节点和当前链表的头节点
    newHead->next = reverseList(head->next);

    // 最终返回新链表的头节点
    return newHead;
}

这个函数会返回一个新的链表，其节点顺序是原始链表的反向。

相关问题

用C++完成逆置一个单链表为一个新表

在C++中，你可以通过迭代或递归的方式来逆置一个单链表。这里我将提供一种常见的迭代方法：

// 首先我们需要定义链表节点结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 迭代法逆置链表
ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL) {  // 特殊情况，链表为空或只有一个元素
        return head;
    }
    
    ListNode* prev = nullptr;  // 初始化前驱指针为NULL
    ListNode* curr = head;   // 当前指针指向头结点

    while (curr != nullptr) {  // 当前节点不为空
        ListNode* nextTemp = curr->next;  // 保存当前节点的下一个节点
        curr->next = prev;  // 将当前节点的next指向前驱节点
        prev = curr;  // 更新前驱节点为当前节点
        curr = nextTemp;  // 更新当前节点为原来保存的下一个节点
    }

    return prev;  // 返回新的头结点
}

在这个函数中，我们遍历链表一次，每次改变当前节点的`next`指向前一个节点，直到遍历完所有节点。最后返回的新头结点就是原链表的尾部。

2、设计一算法，逆置带头结点的动态链表L。要求利用原表的结点空间，并要求用尽可 能少的时间完成。用c++实现头插法给出代码

为了逆置一个带头结点的动态链表，我们可以采用迭代的方式，同时保持对原有节点的利用。这里，我们将通过三个指针 `prev`, `current`, 和 `next` 来实现这个过程。以下是C++的实现，使用头插法：

#include <iostream>

// 定义链表节点
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 递归函数，逆置链表
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {  // 特殊情况，只有一个元素或者空链表
        return head;
    }

    // 将当前节点的next指向前一个节点
    ListNode* temp = head->next;
    head->next = head;  // 将头节点的next指回自身

    // 递归处理剩余部分
    ListNode* newHead = reverseList(temp);  // 返回新头节点

    // 更新临时节点的next指针，使其连接新的头
    temp->next = newHead;

    return newHead;
}

int main() {
    // 创建示例链表
    ListNode* list = new ListNode(1);
    list->next = new ListNode(2);
    list->next->next = new ListNode(3);
    list->next->next->next = new ListNode(4);  // 更多节点...

    // 逆置链表
    ListNode* reversedHead = reverseList(list);

    // 打印逆置后的链表
    ListNode* current = reversedHead;
    while (current != nullptr) {
        std::cout << current->val << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;

    // 释放内存
    while (reversedHead != nullptr) {
        ListNode* temp = reversedHead;
        reversedHead = reversedHead->next;
        delete temp;
    }

    return 0;
}

这段代码首先检查特殊情况，然后依次处理链表的每一个节点，每次都将当前节点的 `next` 指针指向前一个节点。最后返回新的头节点，并释放旧的头节点的空间。