如何在仅能访问当前节点与下一节点的前提下反转单链表

花韻仙語 2026-01-10 00:00:00 次阅读

本文介绍在无法使用额外数据结构（如数组、栈）且仅能通过 `next` 指针遍历链表的情况下，原地反转单链表的经典三指针算法，包含完整实现、逻辑解析与关键注意事项

。

要实现 LinkedList 的 reverse() 方法，核心限制是：不能创建新节点、不能使用辅助容器（如数组或栈），只能通过修改现有节点的 next 引用，以及更新 first 指针来完成反转。你提供的初始代码试图“移动元素值”（如 first.elem = aux.elem），这是错误的方向——题目要求的是逻辑结构反转（即改变指针指向关系），而非元素值的复制或覆盖。一旦修改 elem，不仅破坏原始数据语义，也无法处理不可变对象或含复杂状态的元素。

正确解法基于迭代式三指针技术，空间复杂度 O(1)，时间复杂度 O(n)，全程仅操作指针：

prev：记录已反转部分的头节点（初始为 null）
curr：当前待处理节点（初始为 first）
nextTemp：暂存 curr.next，防止反转过程中链表断裂

算法步骤如下：

从 first 开始遍历；
对每个 curr，先保存其下一节点 nextTemp = curr.next；
将 curr.next 指向 prev（完成当前节点的反向链接）；
更新 prev = curr，curr = nextTemp，继续迭代；
遍历结束后，prev 即为新链表头，赋值给 first。

以下是符合题设类结构的完整实现：

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

    while (curr != null) {
        Node nextTemp = curr.next; // 保存下一个节点
        curr.next = prev;              // 反转当前节点的指针
        prev = curr;                   // 移动 prev 到当前节点
        curr = nextTemp;               // 移动 curr 到下一个节点
    }

    first = prev; // 更新头节点为原链表尾部节点
}

⚠️ 关键注意事项：

切勿尝试交换 elem 字段（如原代码中 first.elem = aux.elem）——这既不满足“反转链表”的语义要求，也违背题目“仅重连 first 和节点间 next”的约束；
空链表（first == null）和单节点链表可被该算法自然兼容，无需额外判断；
nextTemp 的引入必不可少：若直接写 curr.next = prev; curr = curr.next;，将因 curr.next 已被修改而丢失后续节点引用，导致链表截断。

该方法是链表操作的基础范式，深刻体现了“就地逆序”问题中指针操作的精确性与鲁棒性。掌握此模式，可轻松迁移至双向链表反转、部分区间反转等进阶场景。