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

聖光之護 2026-01-10 00:00:00 次阅读

本文讲解如何仅通过调整指针引用（不借助额外数据结构如数组或栈），在单链表中原地完成反转操作，核心是使用三个指针协同移动，逐步翻转相邻节点间的 `next` 指向。

要实现单链表的原地反转，关键在于不创建新节点、不使用辅助容器（如 ArrayList、Stack），仅通过重新链接 next 引用来改变链表方向。由于 LinkedList 类仅暴露 first 引用，且 Node 仅含 elem 和 next 字段（无 prev），我们必须采用迭代指针法——经典「三指针翻转」策略。

其思想是维护三个引用：

prev：指向已反转部分的头节点（初始为 null）；
current：指向当前待处理节点（初始为 first）；
next：临时保存 current.next，防止断链。

每轮迭代中：

保存 current.next 到 next；
将 current.next 指向 prev（完成一次翻转）；
将 prev 更新为 current；
将 current 更新为 next。

当 current 变为 null 时，prev 即为新链表的头节点，最后将 first = prev 即可。

以下是完整、健壮的 reverse() 实现：

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

    while (current != null) {
        next = current.next;   // 保存下一个节点
        current.next = prev;   // 翻转当前节点的 next 指针
        prev = current;        // prev 前进到当前节点
        current = next;        // current 前进到原下一个节点
    }

    first = prev; // 更新头节点为原尾节点（即现在的 prev）
}

⚠️ 注意事项：

空链表或单节点链表：该实现天然兼容（while 循环不执行或仅执行一次，first 正确更新）；
切勿修改 elem 值：题干中你最初的尝试（first.elem = aux.elem）试图“搬运数据”，这既低效又违背“仅重连指针”的要求，也破坏了泛型元素的不可变语义；
时间复杂度 O(n)，空间复杂度 O(1)：严格满足题目“不使用辅助数据结构”的约束。

总结：链表反转的本质不是移动数据，而是逆转引用流向。掌握 prev/current/next 三指针的协作节奏，是解决所有链表原地操作（如检测环、找中点、合并有序链表）的基础范式。