单链表反转：循环与双指针详解

本篇文章向大家介绍《单链表反转详解：循环引用与双指针原理解析》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

本文详解 Java 中 LinkedList 反转时出现 “Found cycle in the ListNode” 错误的根本原因，通过图解对比两种看似相似实则本质不同的实现方式，阐明为何直接复用 `head` 作为新头节点会导致环路，而引入独立 `prev` 指针才能安全完成原地反转。

在链表反转的常见实现中，一个细微的指针操作差异可能导致严重运行时错误——LeetCode 等平台会抛出 Error - Found cycle in the ListNode。该错误并非编译异常，而是测试框架在验证返回链表时检测到环形结构（即某节点的 next 指向了链表中此前已遍历过的节点），从而中断执行。

问题核心在于：是否切断了原链表头部节点的旧 next 引用。

❌ 错误解法（Solution A）：复用 head 导致环路

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode current = head.next;
    while (current != null) {
        ListNode temp = current.next;
        current.next = head; // ⚠️ 危险！将 current 指向原始 head
        head = current;      // 更新 head 为 current
        current = temp;
    }
    return head;
}

关键缺陷：首节点（原 head）的 next 字段从未被修改。
以 [1 → 2 → 3] 为例：

• 初始：head → 1 → 2 → 3，current → 2
• 第一次循环：
  • temp = 3
  • current.next = head → 2.next = 1（此时 1 → 2 且 2 → 1，环已形成！）
  • head = 2，current = 3
• 后续迭代仅处理 3，但 1 ↔ 2 的双向环已固化，无法解除。

最终返回链表在逻辑上是 2 → 1 → 2 → 1 → ...，测试器遍历时无限循环，触发 cycle 检测。

✅ 正确解法（Solution B）：双指针解耦状态

public ListNode reverseList(ListNode head) {
    ListNode curr = head;
    ListNode prev = null; // 显式初始化“前驱”，代表已反转部分的头
    while (curr != null) {
        ListNode temp = curr.next; // 保存下一节点
        curr.next = prev;          // 当前节点指向已反转部分头
        prev = curr;             // 扩展已反转部分：prev 前移
        curr = temp;             // curr 推进到未处理部分
    }
    return prev; // prev 是新链表头（原尾节点）
}

该解法安全的关键在于：

• prev 始终代表已反转子链的头节点（初始为 null，表示空链）；
• 每次 curr.next = prev 将当前节点单向链接到已反转段，不触碰任何未处理节点的 next；
• 原链表的连接被逐步、可控地重定向，无任何节点保留指向未反转区域的引用。

执行 [1→2→3] 过程简述： | 步骤 | curr | prev | 链表状态（从 prev 角度） | |------|------|------|---------------------------| | 初值 | 1 | null | null | | ① | 2 | 1 | 1 → null | | ② | 3 | 2 | 2 → 1 → null | | ③ | null | 3 | 3 → 2 → 1 → null ✅ |

? 注意事项与最佳实践

• 切勿复用原始头节点变量作为新头指针，除非你显式断开其原有 next（如 head.next = null）；
• 双指针模式（prev/curr）是链表原地反转的标准范式，语义清晰、边界安全、不易出错；
• 在调试类似问题时，可借助纸笔绘制每步的节点引用关系，重点关注 next 字段的变更；
• 若使用递归解法，需确保递归基正确设置 head.next = null，否则同样可能残留环。

掌握这一区别，不仅能规避 cycle 错误，更能深化对链表内存模型和指针操作本质的理解——反转的本质不是“移动节点”，而是系统性重写所有 next 指针的方向。

好了，本文到此结束，带大家了解了《单链表反转：循环与双指针详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！