图解Floyd判圈算法 | 判断链表或者迭代函数是否有环 | Java代码

发表于 更新于 分类于 ， 阅读次数： 阅读次数： Waline： 本文字数： 3.7k 阅读时长 ≈ 6 分钟
今天毛毛张分享的是Floyd判圈算法，这是刷LeetCode必备基础算法理论！

1.Floyd判圈算法概述🍇

  • 🍑定义： Floyd判圈算法（Floyd Cycle Detection Algorithm），又称龟兔赛跑算法（Tortoise and Hare Algorithm），是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法🍏

  • 🍒算法思想：

    1. 有限时间内快慢指针必然相遇且在相遇点在环上1️⃣
    2. 相遇点和起点的等速指针将在换的入口出相遇2️⃣

  • 🍓算法作用：

    • 判断迭代函数或者链表上面是否有环1️⃣
    • 如果有环可以找到环的起点2️⃣
    • 如果有换可以计算环的长度3️⃣

  • 🫐这个算法只需要大家了解其原理就行，毛毛张在这里不做严密的逻辑推导，而是通过推介举例的方式来帮助大家理解这个算法

2.如何判断是否有环🍉

有限时间内快慢指针必然相遇且相遇点在环上
  • 由于这个算法的另外一个名称是龟兔赛跑算法，因此毛毛张就拿龟兔赛跑的例子来举例说明：
    • 假设：我们可以假设有乌龟和兔子在一个跑道上比赛跑步，我们默认兔子的跑步速度是快于乌龟的
    • 如果是直线型跑道，两者同时从起点出出发，中途乌龟是永远追不上兔子的，直到涂子到达终点
    • 如果是环形跑道，两者同时从起点出发，经过有限的时间内，兔子会追上乌龟，两者相遇，如果运动过程中兔子的速度是乌龟速度的两倍，那么两者第一次相遇时，兔子的路程就是乌龟路程的两倍
  • 上面这个例子是小学问题中一个很简单的相遇和追及问题，我们回到这个算法本身：
    • 假设兔子就是那个快指针fast，每次走两步，乌龟就是那个慢指针slow，每次走一步
    • 如果链表或者迭代函数没用环，那么快指针迭代到终点，在此过程中，两个指针是不会相遇
    • 如果链表或者迭代函数有环，那么快指针在迭代过程中一定会追上慢指针
  • 图解：

image-20240809104404465

3.如何找到环的起点🍍

相遇点和起点的等速指针将在换的入口出相遇

  • 在上面的问题中，我们假设快指针的速度是慢指针的两倍，那么在相同时间内，第一次相遇的时候，快指针走过的距离为2n，慢指针走过的距离为n，因此单位时间内快指针比慢指针多走一个$n$；于是我们让慢指针回到起点，快指针还在相遇点，即让快指针先走$n$的距离；然后让两个指针的前进速度相同，区分为前指针和后指针

  • 图解：

image-20240810201955223

4.计算环的长度🥭

  • 顺着找到环的入口的思路，我们可以得到方式1：在找到环的入口后，一步一步遍历回到起点时，走过的距离就是环的长度
  • 顺着判断是否有环的思路，我们可以得到方式2： 在找到相遇点之后，继续执行并重新对快慢指针进行计步，直到快慢指针第二次相遇，此时快指针比慢指针多走的距离就是环的长度
  • 方式3： 当快慢指针相遇之后，让快指针一步一步遍历回到相遇点时，走过的距离就是环的长度

5.代码实现🍎

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycle {

    // 生成一个有环的链表，环的长度为5
    public static ListNode createCyclicLinkedList() {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode fourth = new ListNode(4);
        ListNode fifth = new ListNode(5);
        ListNode sixth = new ListNode(6);

        head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = sixth;
        sixth.next = third; // 第三个节点为环的入口，环的长度为5

        return head;
    }

    // 判断链表是否有环
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }

    // 找到环的入口
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // 先判断是否有环
        boolean hasCycle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 如果没有环，返回null
        if (!hasCycle) {
            return null;
        }

        // 找到环的入口
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    // 计算环的长度
    public static int getCycleLength(ListNode head) {
        if (head == null || head.next == null) return 0;

        ListNode slow = head;
        ListNode fast = head;

        // 先找到相遇点
        boolean hasCycle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 如果没有环，返回0
        if (!hasCycle) {
            return 0;
        }

        // 从相遇点开始计算环的长度
        int cycleLength = 0;
        do {
            slow = slow.next;
            cycleLength++;
        } while (slow != fast);

        return cycleLength;
    }

    public static void main(String[] args) {
        ListNode cyclicList = createCyclicLinkedList();

        System.out.println("Has cycle: " + hasCycle(cyclicList));
        ListNode cycleEntry = detectCycle(cyclicList);
        System.out.println("Cycle entry node value: " + (cycleEntry != null ? cycleEntry.val : "No cycle"));
        System.out.println("Cycle length: " + getCycleLength(cyclicList));
    }
}

参考文献

-------------本文结束感谢您的阅读-------------