首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在C++中实现一个反转链表的函数的问题

在C++中实现一个反转链表的函数可以通过迭代或递归的方式来完成。

  1. 迭代方法:
代码语言:txt
复制
#include <iostream>

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;
        curr = nextTemp;
    }
    return prev;
}

int main() {
    // 创建链表
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    // 反转链表
    ListNode* reversedHead = reverseList(head);

    // 输出反转后的链表
    ListNode* curr = reversedHead;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;

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

    return 0;
}

输出结果为:5 4 3 2 1

  1. 递归方法:
代码语言:txt
复制
#include <iostream>

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* reversedHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return reversedHead;
}

int main() {
    // 创建链表
    ListNode* head = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);
    head->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;

    // 反转链表
    ListNode* reversedHead = reverseList(head);

    // 输出反转后的链表
    ListNode* curr = reversedHead;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;

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

    return 0;
}

输出结果为:5 4 3 2 1

以上是在C++中实现反转链表的函数的两种方法。这个函数可以用于将一个单向链表的顺序反转,使得链表的尾部成为头部,头部成为尾部。反转链表在实际开发中常用于解决一些与链表相关的问题,例如链表的遍历、查找、插入、删除等操作。

腾讯云相关产品和产品介绍链接地址:

  • 腾讯云云服务器(CVM):https://cloud.tencent.com/product/cvm
  • 腾讯云云数据库 MySQL 版:https://cloud.tencent.com/product/cdb_mysql
  • 腾讯云云原生容器服务(TKE):https://cloud.tencent.com/product/tke
  • 腾讯云内容分发网络(CDN):https://cloud.tencent.com/product/cdn
  • 腾讯云人工智能(AI):https://cloud.tencent.com/product/ai
  • 腾讯云物联网(IoT):https://cloud.tencent.com/product/iotexplorer
  • 腾讯云移动开发(移动推送、移动分析、移动测试等):https://cloud.tencent.com/product/mobile
  • 腾讯云对象存储(COS):https://cloud.tencent.com/product/cos
  • 腾讯云区块链服务(BCS):https://cloud.tencent.com/product/bcs
  • 腾讯云游戏多媒体引擎(GME):https://cloud.tencent.com/product/gme
  • 腾讯云音视频处理(VOD):https://cloud.tencent.com/product/vod
  • 腾讯云元宇宙(Tencent Real-Time Rendering):https://cloud.tencent.com/product/trtr
页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券