环形链表（LeetCode 141）C语言最佳解题思路

环形链表LeetCode 141C语言解题思路问题描述判断一个链表中是否存在环。解题方法快慢指针法使用两个指针一个快指针每次移动两步一个慢指针每次移动一步。如果链表中存在环快指针最终会追上慢指针如果不存在环快指针会先到达链表尾部。代码实现#include stdbool.h // 链表节点结构体定义题目自带 struct ListNode { int val; struct ListNode *next; }; // 主函数判断链表是否有环 bool hasCycle(struct ListNode *head) { // 边界1空链表 / 只有单个节点无后继直接无环 if (head NULL || head-next NULL) { return false; } // 初始化快慢指针起点都为头节点 struct ListNode *slow head; struct ListNode *fast head; // 循环条件fast和fast-next不能为NULLfast一次走两步防止空指针访问 while (fast ! NULL fast-next ! NULL) { slow slow-next; // 慢走1步 fast fast-next-next; // 快走2步 // 快慢指针相遇证明存在环 if (slow fast) { return true; } } // 循环正常退出说明fast走到链表末尾NULL无环 return false; }代码讲解边界条件检查如果链表为空head NULL或只有一个结点head-next NULL直接返回false因为无法形成环。初始化指针slow指针初始化为head每次移动一步。fast指针初始化为head-next每次移动两步。循环检测在while循环中判断slow和fast是否相遇。如果fast或fast-next为NULL说明链表无环返回false。每次循环中slow移动一步fast移动两步。返回结果如果slow和fast相遇说明链表有环返回true。复杂度分析时间复杂度O(n)无环时快指针最多遍历链表一次。有环时快慢指针会在环内相遇时间复杂度为O(n)。空间复杂度O(1)仅使用了两个指针空间复杂度为常数。