检测链表中的环

最后修改:2025年4月4日

by Deep Jain

1. 引言

单链表是由一系列节点组成的序列，最后一个节点指向 null。但在某些场景下，最后一个节点可能指向了前面的某个节点——这就形成了一个环。

大多数情况下，我们需要检测并处理这种环。本文将聚焦于检测链表中的环以及移除环的方法。

2. 环的检测

下面介绍几种检测链表环的算法。

2.1. 暴力法 —— O(n²) 时间复杂度

这个算法使用两层嵌套循环遍历链表：

  • 外层循环：逐个节点遍历
  • 内层循环：从头节点开始，遍历与外层当前节点相同数量的节点

如果外层循环访问的节点被内层循环访问了两次，说明存在环。反之，如果外层循环到达链表末尾，则说明无环：

public static <T> boolean detectCycle(Node<T> head) {
    if (head == null) {
        return false;
    }

    Node<T> it1 = head;
    int nodesTraversedByOuter = 0;
    while (it1 != null && it1.next != null) {
        it1 = it1.next;
        nodesTraversedByOuter++;

        int x = nodesTraversedByOuter;
        Node<T> it2 = head;
        int noOfTimesCurrentNodeVisited = 0;

        while (x > 0) {
            it2 = it2.next;

            if (it2 == it1) {
                noOfTimesCurrentNodeVisited++;
            }

            if (noOfTimesCurrentNodeVisited == 2) {
                return true;
            }

            x--;
        }
    }

    return false;
}

✅ 优点：空间复杂度为 O(1)
❌ 缺点：处理大型链表时性能极差

2.2. 哈希法 —— O(n) 空间复杂度

这个算法维护一个已访问节点的集合。遍历每个节点时：

  • 检查节点是否存在于集合中
  • 若不存在则加入集合
  • 若存在则说明检测到环

当发现重复节点时，我们就找到了环的起点。此时只需将前一个节点的 next 指针设为 null 即可断开环：

public static <T> boolean detectCycle(Node<T> head) {
    if (head == null) {
        return false;
    }

    Set<Node<T>> set = new HashSet<>();
    Node<T> node = head;

    while (node != null) {
        if (set.contains(node)) {
            return true;
        }
        set.add(node);
        node = node.next;
    }

    return false;
}

⚠️ 时间复杂度：O(n)
⚠️ 空间复杂度：O(n)
❌ 缺点：对于大型链表，空间开销较大

2.3. 快慢指针法

这个算法可以用一个生动的比喻来解释：

想象一个环形跑道，两个人在跑步。第二个人的速度是第一个人的两倍。那么第二个人跑完两圈时，第一个人刚好跑完一圈，两人会在起点相遇。

类似地，我们使用两个指针遍历链表：

  • 慢指针：每次移动一步
  • 快指针：每次移动两步

一旦两个指针都进入环中，它们最终会在某个点相遇。因此，如果两个指针相遇，说明链表存在环：

public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
    if (head == null) {
        return new CycleDetectionResult<>(false, null);
    }

    Node<T> slow = head;
    Node<T> fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            return new CycleDetectionResult<>(true, fast);
        }
    }

    return new CycleDetectionResult<>(false, null);
}

其中 CycleDetectionResult 是一个辅助类，用于保存检测结果：

public class CycleDetectionResult<T> {
    boolean cycleExists;
    Node<T> node;
}

这个方法也被称为**"龟兔赛跑算法"或"Floyd 环检测算法"**。

3. 移除链表中的环

下面介绍几种移除环的方法。所有方法都假设已使用 Floyd 环检测算法发现了环。

3.1. 暴力法

当快慢指针在环中相遇后：

  1. 新增一个指针 ptr 指向头节点
  2. 遍历链表，检查 ptr 是否能从相遇点到达
  3. 当 ptr 到达环的起点时终止（因为这是它第一次进入环）
  4. 找到环的起点后，找到环的终点（指向起点的节点）并将其 next 设为 null
public class CycleRemovalBruteForce {
    private static <T> void removeCycle(
      Node<T> loopNodeParam, Node<T> head) {
        Node<T> it = head;

        while (it != null) {
            if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
                Node<T> loopStart = it;
                findEndNodeAndBreakCycle(loopStart);
                break;
            }
            it = it.next;
        }
    }

    private static <T> boolean isNodeReachableFromLoopNode(
      Node<T> it, Node<T> loopNodeParam) {
        Node<T> loopNode = loopNodeParam;

        do {
            if (it == loopNode) {
                return true;
            }
            loopNode = loopNode.next;
        } while (loopNode.next != loopNodeParam);

        return false;
    }

    private static <T> void findEndNodeAndBreakCycle(
      Node<T> loopStartParam) {
        Node<T> loopStart = loopStartParam;

        while (loopStart.next != loopStartParam) {
            loopStart = loopStart.next;
        }

        loopStart.next = null;
    }
}

❌ 缺点：处理大型链表和长环时性能差，因为需要多次遍历环

3.2. 优化解法 —— 计算环的长度

先定义几个变量：

  • n = 链表总长度
  • k = 头节点到环起点的距离
  • l = 环的长度

它们的关系：k + l = n

算法步骤：

  1. 快慢指针相遇后，计算环的长度 l（固定一个指针，移动另一个直到相遇）
  2. 创建两个指针 ptr1 和 ptr2 指向头节点
  3. 将 ptr2 向前移动 l 步
  4. 同时移动两个指针，它们会在环的起点相遇
  5. 找到环的终点并将其 next 设为 null
public class CycleRemovalByCountingLoopNodes {
    private static <T> void removeCycle(
      Node<T> loopNodeParam, Node<T> head) {
        int cycleLength = calculateCycleLength(loopNodeParam);
        Node<T> cycleLengthAdvancedIterator = head;
        Node<T> it = head;

        for (int i = 0; i < cycleLength; i++) {
            cycleLengthAdvancedIterator 
              = cycleLengthAdvancedIterator.next;
        }

        while (it.next != cycleLengthAdvancedIterator.next) {
            it = it.next;
            cycleLengthAdvancedIterator 
              = cycleLengthAdvancedIterator.next;
        }

        cycleLengthAdvancedIterator.next = null;
    }

    private static <T> int calculateCycleLength(
      Node<T> loopNodeParam) {
        Node<T> loopNode = loopNodeParam;
        int length = 1;

        while (loopNode.next != loopNodeParam) {
            length++;
            loopNode = loopNode.next;
        }

        return length;
    }
}

✅ 优点：比暴力法高效
⚠️ 注意：仍需计算环的长度

3.3. 优化解法 —— 不计算环的长度

通过数学推导优化算法。定义新变量：

  • y = 环起点到相遇点的距离
  • z = 相遇点到环终点的距离（z = l - y）
  • m = 快指针在慢指针进入环前完成的圈数

距离关系：

  • 慢指针距离：k + y
  • 快指针距离：k + ml + y*

快指针速度是慢指针的两倍： k + ml + y = 2*(k + y)*
化简得：*k = (m - 1)l + z

这意味着：**从头节点到环起点的距离 k，等于从相遇点再走 m-1 圈加 z 步**。

算法步骤：

  1. 使用 Floyd 算法检测环并找到相遇点
  2. 创建两个指针：
    • it1 指向头节点
    • it2 指向相遇点
  3. 以相同速度移动两个指针
  4. 它们会在环的起点相遇
  5. 找到环的终点并断开环
public class CycleRemovalWithoutCountingLoopNodes {
    private static <T> void removeCycle(
      Node<T> meetingPointParam, Node<T> head) {
        Node<T> loopNode = meetingPointParam;
        Node<T> it = head;

        while (loopNode.next != it.next) {
            it = it.next;
            loopNode = loopNode.next;
        }

        loopNode.next = null;
    }
}

✅ 最优解：时间复杂度 O(n)，空间复杂度 O(1)，无需计算环长

4. 总结

本文介绍了多种检测链表环的算法，分析了它们的时间和空间复杂度。最后基于 Floyd 环检测算法，展示了三种移除环的方法：

  1. 暴力法：简单但低效
  2. 计算环长法：中等效率
  3. 数学推导法：最优解

对于大型链表，强烈推荐使用快慢指针法检测环 + 数学推导法移除环的组合方案，这是时间和空间复杂度最优的解决方案。

原始标题:Test a Linked List for Cyclicity | Baeldung

« 上一篇： Spring Security OAuth2 新特性：JWT Claims 验证
» 下一篇： Java中整数的位数计算方法