当前位置：首页 > article >正文

蓝桥与力扣刷题（141 环形链表）

article 2025/2/5 19:14:04

题目：给你一个链表的头节点 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
解释：链表中没有环。

第一种解题思路＋代码：（快慢指针）

代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        /**
        思路：
        1.判断链表是否为空或者单链表，是直接返回false
        2.声明快慢指针，遍历链表（快指针速度为一次两步，慢指针速度为一次一步）
        3.当快慢指针相遇时，可以判断出该链表存在环
        4.此时需要将一个指针重新指向链表的头节点
        5.快慢指针同时移动，每次各移动一步，终会在环的入口处相遇
         */

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

        ListNode slowNode = head;
        ListNode fastNode = head;

        //遍历链表（快指针速度为一次两步，慢指针速度为一次一步）
         while(fastNode != null && fastNode.next != null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;

            //快慢指针相遇时，该链表存在环
            if(slowNode == fastNode){
                //将一个指针重新指向链表的头节点
                slowNode = head;
                while(slowNode != fastNode){
                    //快慢指针同时移动，每次各移动一步（是在判断链表存在环之后的快慢指针）
                    slowNode = slowNode.next;
                    fastNode = fastNode.next;
                }
            return true;
            }
         }
         return false;
    }
}

这道题在我解答之后去看了官网和一些大佬的题解，有对快慢指针来判断是否为环形链表相应的图解（作者：Caddy 题解：https://leetcode.cn/problems/linked-list-cycle/solutions/691164/yuan-lai-hui-luo-ji-qing-xi-jian-dan-yi-7o8tx/）

举例一
小汽车和自行车从跑道的起点同时出发
如果没有环道，那么小汽车永远离自行车而去
如果有环道，最终小汽车最终会追上自行车
举例二
大家初高中时候，学校操场的环形跑道上举行万米长跑，跑的快的学生经常会追上跑的慢的学生，也就是跑的快的学生第一次追上跑的慢的学生的时候，实际跑的快的学生比跑的慢的学生多跑了一圈。

第二种解题思路＋代码：（哈希表）引用力扣（作者：数据结构和算法题解：https://leetcode.cn/problems/linked-list-cycle/solutions/438358/3chong-jie-jue-fang-shi-liang-chong-ji-bai-liao-10/）在该篇题解中，作者编写多种方法来解答环形链表，除了快慢指针和哈希表，还有反转链表和链表节点逐个删除的方法，对我而言大佬的多种解法帮我扩充了知识面（大家有兴趣也可以去搜索）。

代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
   public boolean hasCycle(ListNode head) {
    //链表中存在环，那么在遍历链表的过程中，某个节点会重复出现。通过将每个节点添加到哈希集合中，如果某个节点已经存在于集合中，说明链表存在环。
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        //如果重复出现说明有环
        if (set.contains(head))
            return true;
        //否则就把当前节点加入到集合中
        set.add(head);
        head = head.next;
    }
    return false;
    }
}

总结：解答该题所用的快慢指针法只要存在速度差，在移动n次后快慢指针也终会相遇。因此，快慢指针的速度不限定是在2倍之差。另外，在写这道题时，我也苦恼了很久，在使用快慢指针遍历链表确实能够判断出该链表是否存在环，但是如何确定链尾连接到链表中的位置，并返回相应的下标？后面我查询AI时，AI给出了相应的解释：假设链表的起点到环的入口的距离为 x，环的长度为 y。当快慢指针第一次相遇时，慢指针走了 x+y 的距离，而快指针走了 x+2y 的距离（因为快指针比慢指针多走了一圈）。当我们将一个指针重新指向链表的头节点，并让两个指针同时移动时，它们会在环的入口相遇。这是因为：从链表起点到环的入口的距离是 x。从相遇点到环的入口的距离也是 x（因为快指针在环中多走了一圈，所以它在环中走的距离是 y，而从相遇点到环的入口的距离正好是 x）。

查看全文

http://www.kler.cn/a/532809.html