c++中如何实现一个单向链表的反转_c++单链表反转实现方法-C++-PHP中文网

c++中如何实现一个单向链表的反转_c++单链表反转实现方法

裘德小鎮的故事

发布： 2025-10-16 10:55:02

原创

1009人浏览过

答案是迭代法和递归法均可实现链表反转。首先定义包含val和next的ListNode结构；迭代法用prev、curr、nextTemp三个指针遍历链表，逐个反转指针方向，时间O(n)、空间O(1)；递归法在head为空或无后继时返回head，否则递归反转后续节点，并调整head->next->next指向head，同时置head->next为空，最后返回newHead，代码简洁但空间复杂度为O(n)。推荐使用迭代法以避免栈溢出风险。

c++中如何实现一个单向链表的反转_c++单链表反转实现方法

在C++中实现单向链表的反转，核心思路是逐个改变节点的指针方向。不需要创建新节点，只需调整原有节点的next指针，使其指向前一个节点。以下是具体实现方法。

定义链表节点结构

首先定义一个简单的链表节点结构，包含数据域和指向下一个节点的指针：

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

登录后复制

迭代法反转链表

使用三个指针：prev（前一个节点）、curr（当前节点）和nextTemp（临时保存下一个节点），遍历链表并反转指针方向。

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

登录后复制

该方法时间复杂度为O(n)，空间复杂度为O(1)，效率高且易于理解。

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

千图设计室AI海报

千图网旗下的智能海报在线设计平台

172

查看详情

递归法反转链表

递归方式从最后一个节点开始，逐层返回新的头节点，并在回溯过程中修改指针。

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;  // 让下一个节点指向自己
    head->next = nullptr;     // 当前节点的next置空
    return newHead;
}

登录后复制

递归代码简洁，但使用了函数调用栈，空间复杂度为O(n)，对于很长的链表可能引发栈溢出。

基本上就这些。迭代法更推荐用于实际项目，稳定且节省内存。根据需求选择合适的方法即可。

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