「兔了个兔」龟兔赛跑——乌龟和兔子能否相遇？

淡淡的烟草味﹌ 2023-10-04 00:23 19阅读 0赞

### 前言 ###

森林里一年一度的赛跑大赛又开始了，乌龟和兔子又被分到了一组，这次乌龟还能跑过兔子吗？

比赛规则：

1.  乌龟每次移动1个单元格，兔子每次移动2个单元格。
2.  随机出现一条赛道，赛道可能为直线，也可能为含有环线。
3.  如果乌龟和兔子跑进环形区域，则一直在环形区域内前进，直到相遇。
4.  乌龟和兔子都很正经，只往前走，不会后退，也不会相互放水。

根据以上规则，写出程序，判断乌龟是否可以追上兔子(能否相遇)。

![format_png][]

### 思路解析 ###

从比赛规则中可以看出，如果赛道是直线的话，乌龟和兔子是不能相遇的（起点除外）。

所以，乌龟和兔子能否和兔子相遇的关键点在于赛道是否含有环状区域。

这里我们用到“快慢指针”的概念。

> 快慢指针
> 
> 快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

#### 直线赛道 ####

如果是直线赛道，因为兔子比乌龟走的快，只需要判断兔子是否能跑完整个赛道就可以了。

例如，直线赛道由以下节点组成，定义两个指针，兔子为快指针，乌龟为慢指针，如果快指针的下一个节点为`Null`，说明是直线型赛道，这种情况乌龟是追不上兔子的。

![format_png 1][]

#### 环形赛道 ####

如果是环形赛道，例如下图，其中10的下一个节点为5，在这里形成了一个环，一旦进入这个环中是没办法出去的，所以，如果乌龟和兔子在这种赛道上比赛的话，是会出现相遇的情况的。

因为兔子跑的快（快指针），兔子会先进入环中，乌龟跑的慢后进入环中。此时，乌龟和兔子则一直在环中前进，

![format_png 2][]

### 代码实现 ###

经过上面的分析，现在来看一下代码的实现。

#### 定义节点 ####

首先定义一个节点类`Node`，该类有两个属性，一个属性是`value`用来存放节点的值，另一个属性为`next`用来存放下一个节点的内存地址。

方便起见，把属性都定义为了`public`类型。

public class Node {
        // 链表节点的值
        public int value;
        // 链表节点的下一个指针
        public Node next;
    
        public Node(int value) {
            this.value = value;
        }
    }
    复制代码

#### 判断是否有环 ####

判断是否存在环的方法。如果链表为空或小于两位就直接返回`false`了，长度大于两位才判断是否有环。

public static boolean hasCycle (Node node) {
        if (node == null || node.next == null || node.next.next == null) {
            return false;
        }
        // 快指针
        Node quick = node;
        // 慢指针
        Node slow = node;
        // 快指针走的快, 所以判断有没有下一个节点
        while (quick != null && quick.next != null) {
            quick = quick.next.next;
            slow = slow.next;
            // 如果快慢指针为同一个, 说明存在环形区域
            if (slow == quick) {
                return true;
            }
        }
        return false;
    }
    复制代码

#### 生成直链表 ####

使用`for`循环生成`9`个节点，定义一个`temp`变量荣节点链接起来。

public static void main(String[] args) {
        Node node0 = new Node(0);
        Node temp = node0;
        for (int i = 1; i < 10; i++) {
            Node node = new Node(i);
            temp.next = node;
            temp = node;
        }
    
        boolean cycle = hasCycle(node0);
        System.out.println(cycle ? "乌龟和兔子能相遇" : "乌龟和兔子不能相遇");
    }
    复制代码

![format_png 3][]

`Debug`看下代码`node0`的值，可以看出最后一个节点的`next`为`null`。

因为是直链表，所以运行输出结果为“乌龟和兔子不能相遇”。

#### 生成环形链表 ####

先生成一个直链表，再结束时，让最后一个节点指向节点5，所以定义了一个临时变量来存储节点5的地址，这样就形成了一个环。

public static void main(String[] args) {
        Node node0 = new Node(0);
        Node temp = node0;
        Node node5 = null;
        for (int i = 1; i < 10; i++) {
            Node node = new Node(i);
            temp.next = node;
            temp = node;
            if (i == 5) {
                node5 = node;
            }
        }
    
        temp.next = node5;
    
        boolean cycle = hasCycle(node0);
        System.out.println(cycle ? "乌龟和兔子能相遇" : "乌龟和兔子不能相遇");
    }
    复制代码

![format_png 4][]

`Debug`看下代码`node0`的值，可以看出节点9的`next`为节点5，形成了一个环。

因为是环形链表，所以运行输出结果为“乌龟和兔子能相遇”。

### 总结 ###

本文借助“龟兔赛跑”介绍了了快慢指针以及使用快慢指针来判断一个链表中是否含有环，如有错误，欢迎指出。

至于在“龟兔赛跑”中，乌龟和兔子是否能相遇，就看选的赛道啦。

2023年，祝您兔年快乐、前“兔”似锦、大展宏”兔“。

作者：Java星辰  
原文链接：https://juejin.cn/post/7190592456214183992

[format_png]: https://img-blog.csdnimg.cn/img_convert/9b2762cfd39a320f52034d1399f58c85.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/ef8878fe9339bfb34932ff74a44d279d.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/166b09aa9173454a655ffe8e805f3577.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/ff1219b767d00fa082c66b4a5679e394.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/0612281728b1c88051c27a9b14886df9.webp?x-oss-process=image/format,png