如何检测链表中的循环？从哈希表到弗洛伊德算法的深度解析

在数据结构与算法的世界里，链表是我们最熟悉的朋友之一。但有时候，这位朋友会跟我们开个“玩笑”——它可能不再是线性的，而是陷入了一个无限循环之中。想象一下，你正在沿着单链表遍历，希望能最终到达尾部，结果却发现自己像个幽灵一样，在几个节点之间永无止境地打转。这就是我们常说的“循环链表”或链表中存在“环”。

在今天的这篇文章中，我们将深入探讨如何在一个单链表中检测是否存在这样的循环。无论你是在准备技术面试，还是在解决实际的内存泄漏问题（比如循环引用），这都是一个非常实用的技能。我们将从最直观的暴力解法开始，逐步过渡到精妙的算法优化，让你彻底理解背后的逻辑。

什么是链表中的循环？

首先，让我们明确一下我们在处理什么。通常，单链表就像一列火车，每个车厢（节点）只连接到下一个车厢，直到最后一节车厢连接到空气（INLINECODE4e68c3b8 或 INLINECODEae4fe5ca）。但是，如果最后一节车厢连接到了它前面的某一节车厢，火车就进入了环形轨道，列车将永远停不下来。

在计算机科学中，这种现象通常被称为“环形链表”。核心问题在于： 当我们不知道链表长度时，如何高效地判断是否存在这个环形结构？ 如果存在循环，我们的常规遍历算法就会陷入死循环，导致程序崩溃或超时。

让我们通过一个具体的场景来直观理解一下。

#### 场景示例

示例 1：存在循环的情况

> 输入: head: 1 -> 3 -> 4 -> (回到节点 3)

> 输出: true

>

> 解释: 在这个例子中，链表本该在节点 4 结束，但节点 4 的 INLINECODEcbdcb6d3 指针并没有指向 INLINECODEacbef050，而是指回了之前的节点 3。这使得我们在遍历时，会无限循环执行 3 -> 4 -> 3 -> 4…

示例 2：正常链表

> 输入: head: 1 -> 8 -> 3 -> 4 -> NULL

> 输出: false

>

> 解释: 这是一个标准的健康链表。最后一个节点指向 NULL，明确地告诉我们：“旅途到此结束”。

了解了问题定义后，让我们开始动手解决它。我们将从最简单直观的方法入手，然后看看我们能否做得更好。

方法一：使用哈希集合（暴力但直观）

核心思路： 既然循环意味着我们会重复访问同一个节点，那么最直接的想法就是：“让我们把路上见过的每一个节点都记下来！”

我们可以一边遍历链表，一边把经过的节点存入一个哈希集合。每走一步，我们就检查当前节点是否已经在集合里了：

• 如果我们遇到了 INLINECODEc6a0a3c5，说明到达了尽头，返回 INLINECODE38a78bb0（没有循环）。
• 如果我们发现当前节点已经存在于集合中，说明我们来过这里了，肯定有循环，立即返回 true。
• 如果都不满足，就把当前节点加入集合，继续往下走。

这种方法非常容易理解，就像我们在迷宫里留下了脚印。虽然它不是最高效的（需要额外的内存空间），但在很多实际工程场景中，由于实现简单且不易出错，它是一个非常可行的方案。

#### 复杂度分析

• 时间复杂度: O(n)。我们最多只需要遍历链表的每一个节点一次。
• 空间复杂度: O(n)。在最坏的情况下，我们需要把链表中的所有节点都存入哈希集合中。

#### 代码实现

让我们看看如何在不同语言中实现这个逻辑。请注意代码中的注释，它们解释了每一步的关键操作。

C++ 实现

#include 
#include 
using namespace std;

// 定义链表节点
class Node {
public:
    int data;
    Node* next;
    
    // 构造函数
    Node(int x) {
        this->data = x;
        this->next = nullptr;
    }
};

// 检测循环的主函数
bool detectLoop(Node* head) {
    // 创建一个哈希集合来存储访问过的节点地址
    unordered_set visited;
  
    // 遍历链表
    while (head != nullptr) {

        // 关键检查：如果当前节点已经在集合中存在
        // 意味着我们之前访问过它，链表中存在循环
        if (visited.find(head) != visited.end())
            return true;

        // 如果是第一次见到该节点，将其加入集合
        visited.insert(head);

        // 移动到下一个节点
        head = head->next;
    }
    
    // 如果顺利到达链表末尾，说明没有循环
    return false;
}

int main() {
    // 构建测试用例：1 -> 3 -> 4 -> (回到 3)
    Node* head = new Node(1);
    head->next = new Node(3);
    head->next->next = new Node(4);
  
    // 手动制造一个循环
    head->next->next->next = head->next;

    if (detectLoop(head))
        cout << "循环存在 (true)" << endl;
    else
        cout << "无循环 (false)" << endl;

    return 0;
}

Java 实现

import java.util.HashSet;

class Node {
    int data;
    Node next;

    Node(int x) {
        this.data = x;
        this.next = null;
    }
}

class LinkedListDetector {
    static boolean detectLoop(Node head) {
        // 使用 HashSet 来存储节点引用
        HashSet visited = new HashSet();

        while (head != null) {

            // 如果集合中已经包含当前节点，说明找到了环
            if (visited.contains(head))
                return true;

            // 将当前节点加入集合
            visited.add(head);

            // 继续遍历
            head = head.next;
        }
        
        // 遍历结束未发现重复
        return false;
    }

    public static void main(String[] args) {
        // 创建链表：1 -> 3 -> 4
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.next = new Node(4);

        // 制造循环：4 指回 3
        head.next.next.next = head.next;

        if (detectLoop(head))
            System.out.println("循环存在");
        else
            System.out.println("无循环");
    }
}

Python 实现

class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

def detectLoop(head):
    # 使用 Python 的 set 集合来存储节点对象
    visited = set()

    while head is not None:

        # 如果当前节点在集合中，则检测到循环
        if head in visited:
            return True

        # 否则，将节点添加到集合
        visited.add(head)

        # 移动指针
        head = head.next

    # 到达链表尾部
    return False

if __name__ == "__main__":
    # 初始化链表节点
    head = Node(1)
    head.next = Node(3)
    head.next.next = Node(4)

    # 制造循环
    head.next.next.next = head.next

    if detectLoop(head):
        print("true")
    else:
        print("false")

C# 实现

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node next;

    public Node(int x) {
        this.data = x;
        this.next = null;
    }
}

class Program {
    static bool detectLoop(Node head) {
        // HashSet 用于存储节点对象
        HashSet visited = new HashSet();

        while (head != null) {
            
            // 尝试添加节点，如果节点已存在，Add 返回 false
            // 或者使用 Contains 检查
            if (visited.Contains(head))
                return true;

            visited.Add(head);
            head = head.next;
        }
        return false;
    }

    static void Main() {
        Node head = new Node(1);
        head.next = new Node(3);
        head.next.next = new Node(4);
        
        // 制造循环：4 -> 3
        head.next.next.next = head.next;

        if (detectLoop(head))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

虽然哈希集合的方法很好，但在面试或内存受限的环境中，面试官通常会追问：“有没有空间复杂度更低的解法？” 毕竟，O(n) 的空间开销在某些极端情况下（比如链表极长）是昂贵的。让我们来看看那个传奇的算法。

方法二：弗洛伊德循环查找算法（龟兔赛跑）

这是解决链表循环问题的“黄金标准”，也被形象地称为“快慢指针法”或“龟兔赛跑算法”。它的精妙之处在于，它只需要 O(1) 的额外空间。

核心直觉： 想象一下，你在环形跑道上跑步。如果你和一个朋友同时起跑，但你的速度是他的两倍。你会发生什么？

• 你们都从同一点出发。
• 你跑得快，他跑得慢。
• 因跑道是环形的，你最终会从后面“套圈”并再次追上他。

如果跑道是直线的（没有循环），你永远不会回头去追上他，你会一直跑到终点。

算法逻辑：

我们在链表中设置两个指针：

• 慢指针: 每次移动一步 (slow = slow->next)。
• 快指针: 每次移动两步 (fast = fast->next->next)。

只要链表中存在循环，快指针最终一定会进入循环并在里面“追赶”慢指针。因为它们都在同一个闭环里移动，距离会不断缩小，直到快指针在某个节点与慢指针重合（相遇）。如果链表没有循环，快指针会先到达末尾 (NULL)。

#### 为什么快指针不会跳过慢指针？

你可能会问：“快指针跑得那么快，会不会直接跨过慢指针而不相遇？” 答案是不会。

让我们从相对运动的角度思考。快指针相对于慢指针的速度是每步 1（即每次迭代快指针比慢指针多走 1 个节点）。假设快慢指针的距离是 INLINECODE195c99d2。每一步，这个距离 INLINECODEbf9f37a5 就会减少 1。当 d 变成 0 时，它们就相遇了。在环形结构中，它们是“同向而行”，快指针只是在逐步缩短与慢指针的差距，不可能跳过。

#### 复杂度分析

• 时间复杂度: O(n)。如果没有循环，快指针遍历一次；如果有循环，快慢指针在循环内相遇的时间也是线性的。
• 空间复杂度: O(1)。我们只用了两个指针，这才是真正的“常数级空间优化”！

#### 代码实现（C++ 示例）

#include 
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

// 使用弗洛伊德算法检测循环
bool detectLoop(Node* head) {
    // 初始化快慢指针，都从头开始
    Node* slow = head;
    Node* fast = head;

    // 遍历链表
    // 必须检查 fast 和 fast->next 是否为空，因为我们要移动两步
    while (fast != nullptr && fast->next != nullptr) {
        
        // 慢指针走一步
        slow = slow->next;
        
        // 快指针走两步
        fast = fast->next->next;

        // 关键判断：如果在某一步快慢指针相遇了
        // 说明链表中存在循环
        if (slow == fast) {
            return true;
        }
    }

    // 如果快指针到达了末尾，说明没有循环
    return false;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    
    // 创建循环：4 -> 2
    head->next->next->next->next = head->next;

    if (detectLoop(head))
        cout << "循环存在" << endl;
    else
        cout << "无循环" << endl;

    return 0;
}

实战建议与最佳实践

在我们结束之前，我想分享一些在实际开发中处理这个问题时的心得。

1. 空指针异常是你的头号敌人

在使用快慢指针法时，最常见的错误就是忘记检查 INLINECODE3496ca8a 是否为 INLINECODE73e4b12e。因为在执行 INLINECODEea5cfecb 时，如果 INLINECODE76df2bc7 已经是 NULL，程序就会崩溃。永远优先处理边界条件。

2. 何时使用哪种方法？

• 如果你需要快速实现，且内存不是瓶颈： 使用哈希表法。它更直观，不易写错，而且哈希表法还有额外的功能：如果你需要找到循环的入口节点（即循环开始的地方），哈希表法可以直接通过查表返回该节点，而快慢指针法则需要额外的数学推导步骤。
• 如果在面试中或嵌入式系统中： 务必掌握弗洛伊德算法。面试官通常期待看到 O(1) 的空间复杂度。

3. 常见陷阱

在 C++ 或 Java 中，记得我们比较的是节点的引用（内存地址），而不是节点的值 (data)。链表中可能存储两个值相同的节点，但它们位于不同的内存位置，这不代表循环。只有当指针指向同一个对象时，才算循环。

总结

在这篇文章中，我们探讨了检测链表循环的两种主要策略。我们首先学习了利用哈希集合记录路径的“外挂”方式，这让代码逻辑变得非常清晰。随后，我们通过经典的弗洛伊德循环查找算法，领略了利用“快慢指针”在常量空间内解决问题的巧妙之处。

作为一个开发者，理解这些底层逻辑不仅能帮助你通过面试，更能让你在设计系统时对内存管理和数据结构有更深的敬畏。下次当你处理链表操作时，不妨多想一步：“这里会不会产生循环？”这种意识将是区分新手与资深工程师的关键。

希望这篇指南对你有所帮助！继续编码，继续探索！