如何在仅能访问当前节点及其后继节点的前提下原地反转单链表

本文介绍在不使用额外数据结构（如数组、栈）的情况下，仅通过调整指针引用原地反转单链表的算法原理与实现，核心是使用三个指针（prev、curr、next）迭代完成链表方向翻转。

要实现 LinkedList 的 reverse() 方法，关键在于原地修改指针指向，而非交换节点中的元素值（如提问者代码中反复赋值 first.elem 所做的那样

）。该操作不仅逻辑错误（未改变链接关系），还会在链表长度 > 2 时丢失中间元素，且无法真正反转结构。

正确思路是：从头遍历链表，逐个将每个节点的 next 指针由指向后继改为指向前驱。由于单链表无前驱引用，我们需要用三个变量协同维护状态：

• prev：记录已反转部分的新头节点（即当前节点的前一个节点，初始为 null）
• curr：当前正在处理的节点（初始为 first）
• next：暂存 curr.next，防止在修改 curr.next 后丢失后续链路

算法步骤如下：

1. 初始化 prev = null, curr = first
2. 当 curr != null 时循环：
   • 用 next = curr.next 保存下一个待处理节点
   • 将 curr.next 指向 prev（完成当前节点的反向链接）
   • 更新 prev = curr 和 curr = next，推进遍历
3. 循环结束后，prev 指向原链表尾节点，即新链表的头节点 → 将 first = prev

以下是符合题设约束（仅操作 first 引用，不创建辅助集合）的完整实现：

public void reverse() {
    Node prev = null;
    Node curr = first;

    while (curr != null) {
        Node next = curr.next; // 保存下一节点
        curr.next = prev;         // 反转当前节点指针
        prev = curr;              // 前驱前移
        curr = next;              // 当前节点前移
    }
    first = prev; // 更新头节点为原尾节点
}

⚠️ 注意事项：

• 时间复杂度为 O(n)，空间复杂度为 O(1)，严格满足“不使用辅助数据结构”的要求；
• 空链表（first == null）可直接跳过循环，first = prev（即 null）仍保持正确；
• 切勿尝试通过交换 elem 值来“模拟”反转——这违背链表结构本质，且在泛型场景下可能因不可变对象或重载逻辑失效；
• 该算法是链表基础操作的经典范式，熟练掌握有助于理解更复杂的链表变形题（如每 k 个节点反转、检测环等）。

总结：链表反转的本质是指针重定向，而非数据搬运。抓住 prev–curr–next 三指针的状态流转，即可清晰、稳健地完成原地逆序。