小学生都能看懂的 | #链表中环的入口结点#

链表中环的入口结点

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4

链表中环的入口结点

本文主要面向算法小白，如果你追求极致的算法，可以略过本文。

目标

我们需要判断一条项链（链表）是不是闭合成圈的，并且如果项链有环，我们要找到环的入口节点。如果没有环，我们就返回 null。

示例

假设我们有两条项链：

第一条项链：1 → 2，并且环的部分是 3 → 4 → 5 → 3。
第二条项链：1，没有任何珠子指向其他珠子（没有环）。

解释步骤

1. 准备两个“兔子”

想象一下，我们有两个“兔子”，一个跑得慢，一个跑得快。慢兔子每次跳一步，快兔子每次跳两步。

ListNode slow = head; // 慢兔子
ListNode fast = head; // 快兔子

2. 让兔子开始跑

让两个兔子从项链的起点开始跑。慢兔子每次跳一步，快兔子每次跳两步，直到快兔子追上慢兔子。

while (fast != null && fast.next != null) {
    slow = slow.next; // 慢兔子跳一步
    fast = fast.next.next; // 快兔子跳两步
    if (slow == fast) { // 如果快兔子追上了慢兔子
        break;
    }
}

3. 检查是否有环

如果快兔子追上了慢兔子，说明项链有环。否则，说明没有环。

if (fast == null || fast.next == null) {
    return null; // 如果快兔子跑到尽头，说明没有环
}

4. 找到环的入口

如果确定有环，那么我们让快兔子回到起点，然后让快兔子和慢兔子一起以相同的速度前进，直到它们再次相遇。这个相遇的点就是环的入口。

fast = head; // 快兔子回到起点
while (slow != fast) {
    slow = slow.next; // 慢兔子跳一步
    fast = fast.next; // 快兔子跳一步
}

5. 返回结果

当快兔子和慢兔子再次相遇时，它们相遇的地方就是环的入口节点。

return slow; // 返回环的入口节点

示例解析

示例 1

输入：{1,2},{3,4,5}

初始化兔子：
慢兔子和快兔子都站在 1 上。
让兔子跑：
慢兔子跳到 2，快兔子跳到 3。
慢兔子跳到 3，快兔子跳到 5。
慢兔子跳到 4，快兔子跳到 3。
检查是否有环：
快兔子追上了慢兔子，说明有环。
找到环的入口：
快兔子回到起点 1。
慢兔子跳到 3，快兔子跳到 2。
慢兔子跳到 4，快兔子跳到 3。
慢兔子跳到 5，快兔子跳到 4。
慢兔子跳到 3，快兔子跳到 5。
慢兔子跳到 4，快兔子跳到 3。
返回结果：
慢兔子和快兔子再次相遇在 3，所以返回 3。

示例 2

输入：{1},{}

初始化兔子：
慢兔子和快兔子都站在 1 上。
让兔子跑：
快兔子跑到项链的尽头（null）。
检查是否有环：
快兔子没有追上慢兔子，说明没有环。
返回结果：
返回 null。

示例 3

输入：{},{2}

初始化兔子：
慢兔子和快兔子都站在环的起点 2 上。
让兔子跑：
慢兔子跳到 2，快兔子跳到 2。
检查是否有环：
快兔子追上了慢兔子，说明有环。
找到环的入口：
快兔子回到起点 2。
慢兔子跳到 2，快兔子跳到 2。
返回结果：
慢兔子和快兔子再次相遇在 2，所以返回 2。

附上完整代码

import java.util.Arrays;

public class Solution {

    /**
     * 查找链表中环的入口节点。
     * @param head 链表的头节点
     * @return 环的入口节点，如果没有环则返回null
     */
    public ListNode detectCycle(ListNode head) {
        // 初始化两个指针，慢指针和快指针
        ListNode slow = head;
        ListNode fast = head;

        // 让快指针和慢指针开始移动
        while (fast != null && fast.next != null) {
            slow = slow.next; // 慢指针走一步
            fast = fast.next.next; // 快指针走两步
            // 如果相遇，说明有环
            if (slow == fast) {
                break;
            }
        }

        // 如果快指针走到末尾，没有环
        if (fast == null || fast.next == null) {
            return null;
        }

        // 快指针回到起点，两个指针同时走一步，直到再次相遇
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // 返回相遇的节点，即环的入口节点
        return slow;
    }

}

如果本文对你有帮助，请点个免费的赞👍，让它能够帮助到更多的人。

#牛客创作赏金赛#

小学生都能看懂的算法文章被收录于专栏

主要面向小白的算法文章。以小学生都能看懂为目标而编写，顺便巩固下自己。