c++ 链表反转代码 c++单链表反转算法-C++-PHP中文网

c++ 链表反转代码 c++单链表反转算法

穿越時空

发布： 2025-11-28 00:29:16

原创

259人浏览过

链表反转通过调整节点指针实现，提供迭代和递归两种方法。1. 定义节点结构；2. 迭代法用三个指针逐个翻转；3. 递归法从后往前调整指针；4. 测试示例创建链表并反转输出。

c++ 链表反转代码 c++单链表反转算法

链表反转是C++数据结构中的经典问题，核心思路是通过调整每个节点的指针方向来实现反转。下面给出一个完整的单链表反转实现，包含定义、创建、反转和打印操作。

单链表节点定义

首先定义链表节点结构：

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

登录后复制

迭代法反转链表

使用三个指针（prev, curr, next）逐个翻转指向：

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next;  // 保存下一个节点
        curr->next = prev;            // 反转当前节点指针
        prev = curr;                  // 移动 prev 前进一步
        curr = next;                  // 移动 curr 前进一步
    }
    return prev;  // 新的头节点
}

登录后复制

递归法反转链表

递归到底部后，从后往前调整指针：

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

小爱开放平台

小米旗下小爱开放平台

281

查看详情

ListNode* reverseListRecursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

登录后复制

完整测试示例

构建一个简单链表 1->2->3->4 并进行反转：

#include <iostream>
using namespace std;
<p>// 打印链表
void printList(ListNode* head) {
while (head) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}</p><p>int main() {
// 创建链表 1->2->3->4
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);</p><pre class='brush:php;toolbar:false;'>cout << "原链表: ";
printList(head);

head = reverseList(head);  // 反转

cout << "反转后: ";
printList(head);

return 0;

登录后复制

}

输出结果为：
原链表: 1 2 3 4
反转后: 4 3 2 1

两种方法时间复杂度都是 O(n)，空间上迭代法 O(1)，递归法 O(n) 因为调用栈。实际开发中推荐使用迭代法，更稳定且节省内存。

基本上就这些。

以上就是c++++ 链表反转代码 c++单链表反转算法的详细内容，更多请关注php中文网其它相关文章！