环形链表 | LeetCode-141 | LeetCode-142 | Floyd判圈算法 | 双指针 | 哈希集合

Floyd判圈算法练习题

---

LeetCode链接：141. 环形链表1 LeetCode链接：142. 环形链表2

---

题目1：环形链表1

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)（即，常量）内存解决此问题吗？

2.题解

2.1 哈希集合

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 创建一个 HashSet 用于存储访问过的节点
        Set<ListNode> set = new HashSet<>();
        // 初始化当前节点为链表的头节点
        ListNode cur = head;
        // 遍历链表
        while (cur != null) {
            // 如果当前节点已经在 HashSet 中存在，说明存在环
            if (set.contains(cur)) return true;
            set.add(cur);// 否则，将当前节点加入 HashSet
            cur = cur.next;// 将当前节点移向下一个节点
        }
        return false;// 如果遍历完链表，未发现环，返回 false
    }
}

2.2 Floyd判圈算法-双指针

• 写法1： 这种写法对于下面一个题适用，推荐

public boolean hasCycle(ListNode head) {
    // 如果链表为空，或者链表只有一个节点，直接返回 false，因为不可能有环
    if (head == null || head.next == null) return false;
    // 初始化两个指针：慢指针 slow 和 快指针 fast
    ListNode slow = head;           // 慢指针从头节点开始，每次移动一步
    ListNode fast = head;      // 快指针从第二个节点开始，每次移动两步
    // 循环，直到快指针到达链表末尾或找到环
    while (fast != null && fast.next != null) {
        fast = fast.next.next;// 快指针每次移动两步 
        slow = slow.next;// 慢指针每次移动一步
        if (fast == slow) return true; // 如果快指针追上慢指针，说明链表有环
    }
    // 如果循环结束还没有找到环，返回 false，表示链表没有环
    return false;
}

• 写法2：这种写法对于下面一个题目不适用

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 如果链表为空或只有一个节点，直接返回false，因为不可能有环
        if (head == null || head.next == null) return false;
        // 初始化两个指针：慢指针slow指向头节点，快指针fast指向第二个节点
        ListNode slow = head;
        ListNode fast = head.next;

        // 当快指针和慢指针不相遇时，继续遍历链表
        while (slow != fast) {
            // 如果快指针到达链表末尾或者没有下一个节点，说明没有环，返回false
            if (fast == null || fast.next == null) return false;     
            slow = slow.next;// 慢指针每次前进一步            
            fast = fast.next.next;// 快指针每次前进两步
        }
        return true;// 如果快指针和慢指针相遇，则说明链表中有环，返回true
    }
}

题目2：环形链表2

1.题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：你是否可以使用 O(1) 空间解决此题？

2.题解

2.1 哈希集合

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();// 创建一个 HashSet，用于存储遍历过程中访问过的节点
        ListNode cur = head;// 初始化当前节点为链表的头节点
        
        // 遍历链表
        while (cur != null) {
            // 如果当前节点已经在 HashSet 中，说明该节点是环的起点，返回该节点
            if (set.contains(cur)) return cur;
            set.add(cur);// 如果当前节点不在 HashSet 中，将其添加进去
            cur = cur.next;// 继续遍历下一个节点
        }
        
        // 如果遍历完整个链表都没有发现环，返回 null，表示链表中没有环
        return null;
    }
}

2.2 Floyd判圈算法-双指针

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 如果链表为空或者只有一个节点，直接返回 null，因为不可能有环
        if (head == null || head.next == null) return null;

        // 初始化两个指针：慢指针 slow 和 快指针 fast
        ListNode slow = head;
        ListNode fast = head;
        
        boolean hasCycle = false;// 标记是否存在环的布尔变量
        // 快慢指针开始移动
        while (fast != null && fast.next != null) {
            fast = fast.next.next;  // 快指针每次移动两步
            slow = slow.next;       // 慢指针每次移动一步

            // 如果快指针追上慢指针，说明存在环
            if (slow == fast) {
                hasCycle = true;    // 标记存在环
                break;              // 跳出循环
            } 
        }
        if (!hasCycle) return null;// 如果不存在环，直接返回 null

        slow = head;// 重新初始化慢指针，将其设置为头节点
        while (slow != fast) {// 快慢指针再次移动，直到相遇，相遇点就是环的起点
            slow = slow.next;   // 慢指针每次移动一步
            fast = fast.next;   // 快指针每次移动一步
        }

        // 返回环的起点节点
        return fast;
    }
}