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

我正在参加「兔了个兔」创意投稿大赛，详情请看：「兔了个兔」创意投稿大赛

前言

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

比赛规则：

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

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

思路解析

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

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

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

快慢指针

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

直线赛道

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

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

环形赛道

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

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

代码实现

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

定义节点

首先定义一个节点类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 ? "乌龟和兔子能相遇" : "乌龟和兔子不能相遇");
}

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 ? "乌龟和兔子能相遇" : "乌龟和兔子不能相遇");
}

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

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

总结

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

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

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