141.环形链表

LeetCode LeetCode 哈希表 热题100 双指针 链表
发布时间 :
字数:2.8k 阅读 : 评论:
  1. 141.环形链表
    1. 141.1 题目
    2. 141.2 题解
      1. 方法一：使用集合 HashSet 辅助
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：快慢指针（Floyd 判圈算法）
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：递归标记值
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 141.3 代码
    4. 141.4 运行结果

141.环形链表

141.1 题目

给你一个链表的头节点 head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true。否则，返回 false。

示例 1：

链表示例

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

链表示例

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个有效索引。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

141.2 题解

方法一：使用集合 HashSet 辅助

思路

遍历链表，用 HashSet 记录已访问过的节点。如果遇到已经在集合中的节点，说明链表有环；如果遍历到链表末尾（null），说明没有环。

这个方法简单直观，但需要 O(n) 的额外空间。

举个例子：head = [3,2,0,-4]，尾节点连接到第2个节点（索引1）

  • 遍历：3→2→0→-4→2（发现2已在集合中）
  • 返回 true

复杂度分析

  • 时间复杂度：O(n)，每个节点最多访问一次
  • 空间复杂度：O(n)，HashSet 存储所有节点

代码

// 方法一：使用集合HashSet辅助
// 遍历链表 判断节点是否已经访问过 有就返回true 没有就加到HashSet中
static bool HasCycle1(ListNode head)
{
    // 创建一个 HashSet 用于存储已经访问过的节点，HashSet 保证元素的唯一性
    HashSet<ListNode> visited = new HashSet<ListNode>();

    // 遍历链表节点，直到链表末尾
    while (head != null)
    {
        // 如果当前节点已经在 HashSet 中，说明链表有环，返回 true
        if (visited.Contains(head))
        {
            return true;
        }

        // 将当前节点加入 HashSet，表示已经访问过
        visited.Add(head);

        // 移动到链表的下一个节点
        head = head.next;
    }

    // 如果遍历完整个链表都没有发现环，返回 false
    return false;
}

方法二：快慢指针（Floyd 判圈算法）

思路

又称龟兔赛跑算法。慢指针每次走一步，快指针每次走两步。有环时快指针迟早与慢指针相遇；无环时快指针会先碰到 null。实现上令 fast 初始为 head.next、slow 为 head，与「同起点」写法等价。

复杂度分析

  • 时间复杂度：O(n)，每个节点最多被访问常数次。
  • 空间复杂度：O(1)，只使用两个指针。

代码

// 方法二：快慢指针（Floyd 判圈算法，龟兔赛跑）
// Floyd Cycle Detection：快指针每次两步、慢指针每步一步；有环必相遇，无环则快指针先到尾。
static bool HasCycle2(ListNode head)
{
    // 如果链表为空或者只有一个节点，肯定没有环，直接返回 false
    if (head == null || head.next == null)
    {
        return false;
    }

    // 初始化两个指针，一个慢指针 slow 和一个快指针 fast
    ListNode slow = head;
    ListNode fast = head.next;

    // 使用龟兔遍历法，当慢指针和快指针相遇时，说明链表有环，退出循环

    // 第一种龟兔遍历法：当慢指针和快指针相遇时，说明链表有环，返回 true
    while (slow != fast)
    {
        // 如果快指针或者快指针的下一个节点为空，说明没有环，返回 false
        if (fast == null || fast.next == null)
        {
            return false;
        }

        // 移动慢指针一步，移动快指针两步
        slow = slow.next;
        fast = fast.next.next;
    }

    return true;

    // 第二种龟兔遍历法：使用两个循环，当快指针不为空时，继续循环
    while (fast != null)
    {
        // 如果慢指针和快指针相遇，说明链表有环，返回 true
        if (slow == fast)
        {
            return true;
        }

        // 移动慢指针一步，移动快指针一步
        slow = slow.next;
        fast = fast.next;

        // 如果快指针为空，说明链表没有环，返回 false
        if (fast == null)
        {
            return false;
        }

        // 再移动快指针一步
        fast = fast.next;
    }

    // 如果两个循环都没有返回，说明链表没有环，返回 false
    return false;
}

方法三：递归标记值

思路

遍历路径上把节点值改成特殊标记（如 int.MinValue），若再次遇到已标记的值则认为有环。会破坏原链表数据，且题目若允许该值则失效，仅作思路扩展，正式提交不推荐。

复杂度分析

  • 时间复杂度：O(n)，每个节点最多访问一次。
  • 空间复杂度：O(n)，递归栈深度。

代码

// 方法三：递归标记值
// 判断当前节点值是不是 int.MinValue，不是的话将当前节点的值标记为 int.MinValue，表示已经访问过，递归下一节点
static bool HasCycle3(ListNode head)
{
    // 如果链表为空或者只有一个节点，肯定没有环，直接返回 false
    if (head == null || head.next == null)
    {
        return false;
    }

    // 如果当前节点的值已经被标记为 int.MinValue，说明链表有环，返回 true
    if (head.val == int.MinValue)
    {
        return true;
    }

    // 将当前节点的值标记为 int.MinValue，表示已经访问过
    head.val = int.MinValue;

    // 递归调用 HasCycle3 方法，传入下一个节点
    return HasCycle3(head.next);
}

141.3 代码

using System;
using System.Collections.Generic;

class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int x)
    {
        val = x;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个链表的头节点 head ，判断链表中是否有环。
        // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
        // 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
        // 注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
        // 如果链表中存在环 ，则返回 true。 否则，返回 false。

        // 示例 1：
        // 输入：head = [3,2,0,-4], pos = 1
        // 输出：true
        // 解释：链表中有一个环，其尾部连接到第二个节点。

        // 示例 2：
        // 输入：head = [1,2], pos = 0
        // 输出：true
        // 解释：链表中有一个环，其尾部连接到第一个节点。

        // 示例 3：
        // 输入：head = [1], pos = -1
        // 输出：false
        // 解释：链表中没有环。

        #endregion

        #region 测试

        // 示例 1
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 使链表形成环

        bool result1 = HasCycle1(node1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        bool result1_2 = HasCycle2(node1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");
        bool result1_3 = HasCycle3(node1);
        Console.WriteLine($"示例1 方法3 输出：{result1_3}");

        // 示例 2
        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(2);

        node5.next = node6;
        node6.next = node5; // 使链表形成环

        bool result2 = HasCycle1(node5);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        bool result2_2 = HasCycle2(node5);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");
        bool result2_3 = HasCycle3(node5);
        Console.WriteLine($"示例2 方法3 输出：{result2_3}");

        // 示例 3
        ListNode node7 = new ListNode(1);

        bool result3 = HasCycle1(node7);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        bool result3_2 = HasCycle2(node7);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");
        bool result3_3 = HasCycle3(node7);
        Console.WriteLine($"示例3 方法3 输出：{result3_3}");

        #endregion
    }

    #region 答案

    // 方法一：使用集合HashSet辅助
    // 遍历链表 判断节点是否已经访问过 有就返回true 没有就加到HashSet中
    static bool HasCycle1(ListNode head)
    {
        // 创建一个 HashSet 用于存储已经访问过的节点，HashSet 保证元素的唯一性
        HashSet<ListNode> visited = new HashSet<ListNode>();

        // 遍历链表节点，直到链表末尾
        while (head != null)
        {
            // 如果当前节点已经在 HashSet 中，说明链表有环，返回 true
            if (visited.Contains(head))
            {
                return true;
            }

            // 将当前节点加入 HashSet，表示已经访问过
            visited.Add(head);

            // 移动到链表的下一个节点
            head = head.next;
        }

        // 如果遍历完整个链表都没有发现环，返回 false
        return false;
    }


    // 方法二：快慢指针Floyd判圈算法（龟兔赛跑算法)
    // loyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。
    // 简单原理就是用两个指针，一个快，一个慢。
    // 快指针一次移动两步；慢指针一次移动一步。如果存在环，那么快指针始终可以追上慢指针，即两个指针一定会出现指向同一个节点的状态，就好像赛跑中被套圈。 
    static bool HasCycle2(ListNode head)
    {
        // 如果链表为空或者只有一个节点，肯定没有环，直接返回 false
        if (head == null || head.next == null)
        {
            return false;
        }

        // 初始化两个指针，一个慢指针 slow 和一个快指针 fast
        ListNode slow = head;
        ListNode fast = head.next;

        // 使用龟兔遍历法，当慢指针和快指针相遇时，说明链表有环，退出循环

        // 第一种龟兔遍历法：当慢指针和快指针相遇时，说明链表有环，返回 true
        while (slow != fast)
        {
            // 如果快指针或者快指针的下一个节点为空，说明没有环，返回 false
            if (fast == null || fast.next == null)
            {
                return false;
            }

            // 移动慢指针一步，移动快指针两步
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;

        // 第二种龟兔遍历法：使用两个循环，当快指针不为空时，继续循环
        while (fast != null)
        {
            // 如果慢指针和快指针相遇，说明链表有环，返回 true
            if (slow == fast)
            {
                return true;
            }

            // 移动慢指针一步，移动快指针一步
            slow = slow.next;
            fast = fast.next;

            // 如果快指针为空，说明链表没有环，返回 false
            if (fast == null)
            {
                return false;
            }

            // 再移动快指针一步
            fast = fast.next;
        }

        // 如果两个循环都没有返回，说明链表没有环，返回 false
        return false;
    }

    // 方法三：递归标记值
    // 判断当前节点值是不是 int.MinValue，不是的话将当前节点的值标记为 int.MinValue，表示已经访问过，递归下一节点
    static bool HasCycle3(ListNode head)
    {
        // 如果链表为空或者只有一个节点，肯定没有环，直接返回 false
        if (head == null || head.next == null)
        {
            return false;
        }

        // 如果当前节点的值已经被标记为 int.MinValue，说明链表有环，返回 true
        if (head.val == int.MinValue)
        {
            return true;
        }

        // 将当前节点的值标记为 int.MinValue，表示已经访问过
        head.val = int.MinValue;

        // 递归调用 HasCycle3 方法，传入下一个节点
        return HasCycle3(head.next);
    }

    #endregion
}

141.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例1 方法3 输出：True
示例2 方法1 输出：True
示例2 方法2 输出：True
示例2 方法3 输出：True
示例3 方法1 输出：False
示例3 方法2 输出：False
示例3 方法3 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏