JavaScript 程序：查找链表中的循环长度

在计算机科学中，链表是一种常见的数据结构。而判断链表中是否存在循环并确定其长度，是一个经典的算法问题。本文将探讨如何使用 JavaScript 编写程序来查找链表中的循环长度。

让我们了解一下链表的基本结构。链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。当链表中某个节点的下一个节点引用指向了链表中已经访问过的节点时，就形成了循环。

要检测链表中的循环，可以使用快慢指针（Floyd 判圈算法）。慢指针每次移动一个节点，而快指针每次移动两个节点。如果链表存在循环，快指针最终会追上慢指针。

下面是实现检测链表是否存在循环的 JavaScript 代码：

function hasCycle(head) {
    let slow = head;
    let fast = head;

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

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

当确定链表存在循环后，我们需要计算循环的长度。一旦快慢指针相遇，我们可以从相遇点开始，使用一个指针遍历循环，同时记录遍历的节点数，直到再次回到相遇点，此时记录的节点数就是循环的长度。

以下是计算循环长度的 JavaScript 代码：

function cycleLength(head) {
    let slow = head;
    let fast = head;
    let hasCycleFlag = false;

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

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

    if (!hasCycleFlag) {
        return 0;
    }

    let ptr = slow;
    let length = 1;
    ptr = ptr.next;

    while (ptr!== slow) {
        length++;
        ptr = ptr.next;
    }

    return length;
}

通过上述代码，我们不仅能够判断链表中是否存在循环，还能准确计算出循环的长度。这种方法在处理链表相关问题时非常实用，例如数据验证、内存管理等场景。掌握这些算法，有助于我们更好地理解和处理复杂的数据结构，提升编程能力和解决实际问题的能力。无论是新手还是有经验的开发者，对链表循环检测和长度计算的深入理解都将为日常编程工作带来极大的便利。