算法：判断链表是否有环

/*** @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;
}

1. 快慢指针步长比例分析

   • 快指针走两步、慢指针走一步的原理
     • 假设链表存在环，环的长度为nn。设慢指针进入环时，快指针与慢指针的距离为mm（0⩽m<n0⩽m<n）。
     • 因为快指针每次比慢指针多走一步，所以每一轮循环，快指针与慢指针的距离会减少11。
     • 最终，经过mm轮循环后，快指针和慢指针必然会相遇。
   • 其他可能的步长比例
     • 例如，快指针走三步，慢指针走一步。
     • 但是这种情况下会有一些特殊情况需要考虑。假设环的长度nn和初始距离mm存在某些特定关系时，可能会出现快指针“跳过”慢指针而不相遇的情况。
     • 例如，当环长n=4n=4，初始距离m=2m=2时，快指针走三步，慢指针走一步，可能会出现快指针和慢指针一直无法相遇的情况。
   • 快指针走两步、慢指针走一步的优势
     • 这种步长比例简单且能稳定地判断链表是否有环，不会出现特殊情况导致判断错误。所以在实际应用中被广泛使用。