141.环形链表

LeetCode LeetCode 哈希表 双指针 链表
发布时间 :
字数:2.6k 阅读 : 评论:
  1. 141.环形链表
    1. 141.1 题目
    2. 141.2 题解
      1. 使用集合HashSet辅助
      2. 快慢指针Floyd判圈算法(龟兔赛跑算法)
      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辅助
// 遍历链表 判断节点是否已经访问过 有就返回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判圈算法(龟兔赛跑算法)

// 方法二：快慢指针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);
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏