C++如何实现一个单向链表的反转？（面试题示例）-C++-PHP中文网

C++如何实现一个单向链表的反转？（面试题示例）

尼克

发布： 2025-12-12 19:05:03

原创

648人浏览过

迭代法是最稳妥解法：用prev、curr、nextTemp三指针边遍历边调整next指向，时间O(n)、空间O(1)，核心是让当前节点指向已处理的前驱，最终prev即新头。

c++如何实现一个单向链表的反转？（面试题示例）

用三个指针迭代翻转，时间复杂度 O(n)，空间复杂度 O(1) —— 这是面试中最稳妥、最常被期待的解法。

核心思路：边遍历边调整指针方向

原链表是 head → node1 → node2 → node3 → nullptr，反转后要变成 nullptr ← head ← node1 ← node2 ← node3（此时 node3 成为新头）。关键不是“把节点搬来搬去”，而是让每个节点的 next 指向前一个已处理的节点。

需要三个变量配合：

prev：记录「当前节点的前一个节点」，初始为 nullptr
curr：当前正在处理的节点，初始为 head
nextTemp：暂存 curr->next，避免断链后找不到后续

代码实现（带注释）

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    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* nextTemp = curr->next; // 先保存下一个节点
    curr->next = prev;               // 当前节点指向前面
    prev = curr;                     // prev 前进一步
    curr = nextTemp;                 // curr 前进一步
}

return prev; // prev 最终停在原链表尾，即新链表头

登录后复制

}

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

情感家园企业站5.0 多语言多风格版

一套面向小企业用户的企业网站程序！功能简单，操作简单。实现了小企业网站的很多实用的功能，如文章新闻模块、图片展示、产品列表以及小型的下载功能，还同时增加了邮件订阅等相应模块。公告，友情链接等这些通用功能本程序也同样都集成了！同时本程序引入了模块功能，只要在系统默认模板上创建模块，可以在任何一个语言环境（或任意风格）的适当位置进行使用！

查看详情

常见易错点提醒

忘记保存 curr->next 就直接改 curr->next = prev，导致后续节点丢失
返回了 curr（循环结束时为 nullptr）而不是 prev
没处理空链表（head == nullptr）的情况 —— 实际上上述代码天然支持，无需额外判断
递归写法虽简洁但有栈溢出风险，面试中建议先写迭代，再提递归作为补充

递归版本（理解用，非首选）

思想：先反转 head->next 开始的子链，再把 head 接到子链尾部。需注意边界和连接逻辑：

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
<pre class="brush:php;toolbar:false;">ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;

登录后复制

}

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

基本上就这些。写对迭代三步（存、改、移）就不容易错。

以上就是C++如何实现一个单向链表的反转？（面试题示例）的详细内容，更多请关注php中文网其它相关文章！