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

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

用三个指针迭代翻转，时间复杂度 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++免费学习笔记（深入）”；

标签： node 栈 c++