当前位置：首页 > 文章列表 > 文章 > java教程 > 单链表反转：循环与双指针详解

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

2026-01-28 19:30:41 0浏览收藏

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

如何正确反转单链表：深入解析循环引用错误与双指针解法原理

本文详解 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 ✅ |