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

日期：2025-12-12 00:00 / 作者：尼克

迭代法是最稳妥解法：用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) {} };

ListNode reverseList(ListNode head) { ListNode prev = nullptr; ListNode curr = head;

while (curr != nullptr) {
    ListNode* nextTemp = curr->next; // 先保存下一个节点
    curr->next = prev;               // 当前节点指向前面
    prev = curr;                     // prev 前进一步
    curr = nextTemp;                 // curr 前进一步
}

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

}

常见易错点提醒

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

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

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

ListNode* reverseList(ListNode* head) { if (!head || !head->next) return head;

ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;

}

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