算法：判断链表是否有环

/** * @brief 判断链表是否有环 * * 该函数使用快慢指针法来判断链表中是否存在环。 * 快指针每次移动两步，慢指针每次移动一步。 * 如果链表中存在环，那么快指针最终会追上慢指针； * 如果链表中不存在环，快指针会先到达链表末尾。 * * @param head 指向链表头节点的指针 * @return int 若链表有环返回 1，否则返回 0 */ int isCycle(Node *head) { // 初始化快指针，指向链表的头节点 Node *fast = head; // 初始化慢指针，指向链表的头节点 Node *slow = head; // 循环条件：快指针不为空且快指针的下一个节点也不为空 while(fast != NULL && fast->next != NULL) { // 快指针每次移动两步 fast = fast->next->next; // 慢指针每次移动一步 slow = slow->next; // 如果快指针和慢指针相遇，说明链表中有环 if (fast == slow) { return 1; } } // 若循环结束后未相遇，说明链表中无环 return 0; } 快慢指针步长比例分析 快指针走两步、慢指针走一步的原理 假设链表存在环，环的长度为nn。设慢指针进入环时，快指针与慢指针的距离为mm（0⩽m<n0⩽m<n）。因为快指针每次比慢指针多走一步，所以每一轮循环，快指针与慢指针的距离会减少11。最终，经过mm轮循环后，快指针和慢指针必然会相遇。 其他可能的步长比例 例如，快指针走三步，慢指针走一步。但是这种情况下会有一些特殊情况需要考虑。假设环的长度nn和初始距离mm存在某些特定关系时，可能会出现快指针“跳过”慢指针而不相遇的情况。例如，当环长n=4n=4，初始距离m=2m=2时，快指针走三步，慢指针走一步，可能会出现快指针和慢指针一直无法相遇的情况。 快指针走两步、慢指针走一步的优势 这种步长比例简单且能稳定地判断链表是否有环，不会出现特殊情况导致判断错误。所以在实际应用中被广泛使用。