c++中如何反转链表_c++链表反转实现方法

反转链表有两种主要方法：迭代法和递归法。迭代法使用三个指针遍历链表，时间复杂度O(n)，空间复杂度O(1)；递归法通过递归调用到达链表尾部后逐层反转，时间复杂度O(n)，空间复杂度O(n)。推荐在生产环境中使用迭代法，递归法更利于理解递归思想。测试示例显示输入链表1→2→3经反转后输出为3 2 1，验证了算法正确性。实际应用中需注意内存管理以避免泄漏。

在C++中反转链表是一个常见的数据结构操作，主要用于单向链表。实现方式主要有两种：迭代法和递归法。下面详细介绍这两种方法的实现思路和代码。

定义链表节点结构

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

方法一：迭代法反转链表

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next; // 保存下一个节点
        curr->next = prev; // 反转当前指针
        prev = curr; // 移动 prev 前进
        curr = nextTemp; // 移动 curr 前进
    }
    return prev; // prev 最终指向原链表的最后一个节点，即新头节点
}

方法二：递归法反转链表

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; // 返回新的头节点
}

爱图表

AI驱动的智能化图表创作平台

99

查看详情

立即学习“C++免费学习笔记（深入）”；

使用示例与测试

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    head = reverseList(head); // 反转链表

    // 打印结果：3 2 1
    ListNode* p = head;
    while (p) {
        std::cout << p->val << " ";
        p = p->next;
    }
    return 0;
}

基本上就这些。迭代法更推荐用于生产环境，递归法适合理解递归思想。实际应用中注意内存释放，避免泄漏。

以上就是c++++中如何反转链表_c++链表反转实现方法的详细内容，更多请关注php中文网其它相关文章！