Day06

算法每日一题

原题链接：https://leetcode.cn/problems/linked-list-cycle/description/?envType=problem-list-v2&envId=2cktkvj

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * 检查链表是否有环
 * @param {ListNode} head - 链表的头节点
 * @return {boolean} - 如果链表有环则返回 true，否则返回 false
 */
var hasCycle = function(head) {
    // 如果链表为空或只有一个节点，直接返回 false
    if (head == null || head.next == null) {
        return false;
    }

    // 初始化快慢指针
    let fast = head.next; // 快指针从第二个节点开始
    let slow = head;      // 慢指针从第一个节点开始

    // 当快慢指针不相等时，继续循环
    while (fast != slow) {
        // 如果快指针到达链表末尾，说明没有环
        if (fast == null || fast.next == null) {
            return false;
        }

        // 快指针每次移动两步
        fast = fast.next.next;
        // 慢指针每次移动一步
        slow = slow.next;
    }

    // 如果快慢指针相遇，则说明链表有环
    return true;
};

在解决链表是否有环的问题时，最直观的方法是使用哈希表来记录访问过的节点，但这需要额外的空间来存储节点信息。在这里，我们使用了一种优化算法——Floyd 判圈算法，也被称为龟兔赛跑算法。

龟兔赛跑算法的基本思想
我们定义两个指针：一个快指针和一个慢指针。快指针每次移动两步，而慢指针每次移动一步。如果链表没有环，快指针最终会到达链表的末尾。如果链表有环，快指针会在环中不断循环，而慢指针进入环后，快指针会在某个时刻与慢指针相遇，这就可以证明链表存在环。

确定环的起始节点
除了检测链表是否有环外，龟兔赛跑算法还可以用来确定环的起始节点。当快慢指针第一次相遇时，我们将慢指针移回链表的起始节点，同时将快指针保持在相遇点。然后，让两指针以相同的速度（每次移动一步）重新开始移动。当它们再次相遇时，相遇点即为环的起始节点。