C++如何实现链表反转_C++单链表反转算法图解与代码-C++-PHP中文网

C++如何实现链表反转_C++单链表反转算法图解与代码

尼克

发布： 2025-12-09 13:01:02

原创

709人浏览过

链表反转通过三个指针prev、curr、next实现，依次调整节点指向，最终使链表倒序。初始化prev为nullptr，curr为头节点，遍历中保存next节点，将curr→next指向prev，逐步前移，直至curr为空，此时prev指向新头节点。整个过程时间复杂度O(n)，空间复杂度O(1)。

c++如何实现链表反转_c++单链表反转算法图解与代码

链表反转是C++数据结构中的经典问题，核心在于调整每个节点的指针方向。不需要创建新节点，只需改变原有节点的 next 指向，就能将整个链表倒序。

链表反转的基本思路

反转单链表的关键是使用三个指针：

prev：指向已反转部分的头节点，初始为 nullptr
curr：指向当前正在处理的节点，初始为原链表头节点
next：临时保存 curr 的下一个节点，防止断链

通过遍历链表，逐步将每个节点的 next 指向前一个节点，直到整个链表完成反转。

图解反转过程（简化步骤）

假设原链表为：1 → 2 → 3 → nullptr

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

面多多

面试鸭推出的AI面试训练平台

219

查看详情

初始化：prev = nullptr, curr = 1
处理节点 1：
- 保存 next = curr→next（即 2）
- 令 curr→next = prev（即 1→nullptr）
- 更新 prev = curr（prev 指向 1），curr = next（curr 指向 2）
处理节点 2：
- 保存 next = 3
- 令 2→next = 1
- prev = 2, curr = 3
处理节点 3：
- 保存 next = nullptr
- 令 3→next = 2
- prev = 3, curr = nullptr
循环结束，prev 指向新的头节点（原尾节点）

最终链表变为：3 → 2 → 1 → nullptr

C++代码实现

以下是完整的链表反转函数实现：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
<p>ListNode<em> reverseList(ListNode</em> head) {
ListNode<em> prev = nullptr;
ListNode</em> curr = head;</p><pre class="brush:php;toolbar:false;">while (curr != nullptr) {
    ListNode* next = curr->next;  // 保存下一个节点
    curr->next = prev;            // 反转当前节点指针
    prev = curr;                  // 移动 prev 前进一步
    curr = next;                  // 移动 curr 前进一步
}

return prev;  // 新的头节点

登录后复制

}

使用示例

如何调用该函数：

int main() {
    // 创建链表 1→2→3
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
<pre class="brush:php;toolbar:false;">head = reverseList(head);  // 反转后 head 指向 3

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

return 0;

登录后复制

}

基本上就这些。理解指针移动顺序是关键，尤其是先保存 next 再修改指针，避免访问已释放内存。整个算法时间复杂度 O(n)，空间复杂度 O(1)，高效且实用。

以上就是C++如何实现链表反转_C++单链表反转算法图解与代码的详细内容，更多请关注php中文网其它相关文章！