C++ 链表反转代码实现_C++数据结构面试必问-C++-PHP中文网

C++ 链表反转代码实现_C++数据结构面试必问

穿越時空

发布： 2025-12-05 06:43:22

原创

424人浏览过

链表反转的两种实现方法为迭代法和递归法。1. 迭代法使用三个指针prev、curr、next，逐个翻转节点指向，最后返回prev作为新头节点。2. 递归法从最后一个节点开始，将后一节点的next指向当前节点，并断开当前节点next，最终返回新的头节点。代码包含完整定义、反转函数及测试示例，构造链表1→2→3→4，反转后输出4 3 2 1，验证正确性。两种方法均需处理空链表或单节点边界情况，避免空指针访问，建议结合图示理解指针变化过程。

c++ 链表反转代码实现_c++数据结构面试必问

链表反转是C++数据结构面试中的高频考点，考察对指针操作和逻辑思维的理解。实现方式主要有迭代法和递归法两种，下面分别给出清晰、可运行的代码实现。

迭代法反转单链表

使用三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点），逐个翻转指针方向。

#include <iostream>
using namespace std;
<p>// 链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};</p><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;  // 新的头节点

登录后复制

}

递归法反转单链表

递归到底部后，从最后一个节点开始重新连接，关键在于将下一个节点的 next 指向当前节点，并断开当前节点的 next。

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

Sider

多功能AI浏览器助手，帮助用户进行聊天、写作、阅读、翻译等

3249

查看详情

// 递归反转链表
ListNode* reverseListRecursive(ListNode* head) {
    // 递归终止条件
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
<pre class='brush:php;toolbar:false;'>// 递归反转剩余部分
ListNode* newHead = reverseListRecursive(head->next);

// 调整指针：将后一个节点指向当前节点
head->next->next = head;
head->next = nullptr;  // 当前节点变为尾节点

return newHead;  // 返回新的头节点

登录后复制

}

完整测试示例

构造一个简单链表 1→2→3→4，反转后输出结果验证正确性。

// 打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
<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;

登录后复制

}

上述代码在主流编译器（如g++）下可直接运行，输出为：
原链表: 1 2 3 4
反转后: 4 3 2 1

基本上就这些。掌握这两种写法，尤其理解指针变化过程，面试中就能从容应对。注意空链表和单节点情况的处理，避免访问空指针。调试时建议画图辅助理解每一步的连接关系。

以上就是C++ 链表反转代码实现_C++数据结构面试必问的详细内容，更多请关注php中文网其它相关文章！