LeetCode 补充题 188. 链表断环

约 4 分钟
文章信息 3 个分类 2 个标签
分类
补充题 中等 滴滴
标签
双指针 链表

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 142. 环形链表 II

:::

给定可能带环的单链表，若存在环，将环中指向入口的那条边断开，使从原表头出发能恰好访问每个原有可达节点一次。

无环时保持不变，返回原表头。

示例 1：

输入： 节点值 = [1,2,3,4]，尾节点的 next 指向第二个节点
输出： head = [1,2,3,4]，尾节点的 next = null
解释： 断开 4 指向 2 的边，所有节点仍可从原表头恰好访问一次。

示例 2：

输入： 一个值为 1 的节点，next 指向自己
输出： head = [1]，next = null
解释： 断开自环后，原节点保留。

提示：

  • 链表可能有环。
  • 只能断开环中指向入口的那条边，保留全部原有可达节点。
  • 无环时保持原样。

题意分析

只要消除环并不够，还必须保留从原表头可达的全部节点。应先定位环入口，再断开环中最后回到入口的边；在任意相遇点直接断开可能使后续部分不可达。

解法：Floyd 定位入口后断开闭合边

核心思路

[!blue]

快指针每次两步、慢指针每次一步，先移动再比较；快指针遇空说明无环，原样返回。有环相遇时，设入环前长度为 a、入口到相遇点距离为 b、环长为 c，路程差给出 a+b 是 c 的整数倍。

将一个指针放回表头，两个指针同步走一步，走过 a 步时就在环入口相遇。此时沿环继续寻找 tail.next == entry 的节点，把这一条连接置空。

原头到入口的前缀以及完整的一圈环都仍按原顺序可达，只去掉重复回到入口的边。自环时入口本身就是 tail，一次置空即可；返回值始终是原表头。

解题步骤

  1. 快慢指针先移动再比较，无环时立即返回原头。
  2. 相遇后将一个指针放回头部，两者同速前进找到入口。
  3. 从入口沿环寻找指向入口的节点，只将该节点 next 置空。

代码实现

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode breakCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null) {
                return head;
            }

            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        slow = head;

        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        ListNode tail = slow;

        while (tail.next != slow) {
            tail = tail.next;
        }

        tail.next = null;

        return head;
    }
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func breakCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for {
        if fast == nil || fast.Next == nil {
            return head
        }
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    tail := slow
    for tail.Next != slow {
        tail = tail.Next
    }
    tail.Next = nil
    return head
}

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：额外空间 $O(1)$。

关键点总结

[!green]

相遇点不一定是入口；必须断开入口在环中的前驱边，才能保留从原头可达的全部节点。

易错点总结

[!yellow]

不能直接把相遇点或入口的next置空，否则可能漏掉环上的其他节点。

相似题目

题目 难度 关联与区别
142. 环形链表 II 中等 复用环入口定位，本题再找到环中入口的前驱，只断开那条闭合边。
141. 环形链表 简单 先用快慢指针判断有无环；本题还要保留所有原有可达节点并恢复无环结构。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/36343329
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！