【数据结构实战】判断链表是否有环：快慢指针法（Floyd 判圈算法）

一、问题描述给定一个单向链表判断链表中是否存在环。如果链表有环输出「有环」如果链表无环输出「无环」什么是环链表最后一个节点的 next 不再指向 NULL而是指向链表前面的某个节点形成闭环。二、解题思路快慢指针法Floyd 判圈算法这是最经典、最常用、空间复杂度 O (1) 的解法。核心思想定义两个指针慢指针 slow每次走1 步快指针 fast每次走2 步从头节点一起出发如果有环快指针一定会在环里追上并相遇慢指针如果无环快指针会先走到 NULL结束遍历图解如下为什么一定会相遇可以想象成在环形跑道上跑步一个快一个慢只要跑道是环快的一定会套圈追上慢的。三、核心代码1. 链表节点结构typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } Node;2. 判断是否有环核心函数int isCycle(Node *head) { Node *fast head; Node *slow head; while (fast ! NULL fast-next ! NULL) { slow slow-next; // 慢指针走1步 fast fast-next-next; // 快指针走2步 if (fast slow) { // 相遇 有环 return 1; } } return 0; // 快指针到末尾 无环 }关键点循环条件必须判断fast ! NULL fast-next ! NULL防止越界相遇就直接返回有环效率很高四、完整可运行代码C 语言创建链表、构造环、测试、输出结果#include stdio.h #include stdlib.h // 1. 链表节点定义 typedef struct Node { int data; struct Node *next; } Node; // 2. 创建头节点 Node *initList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; return head; } // 3. 尾插法添加节点 Node *insertTail(Node *tail, int data) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data data; newNode-next NULL; tail-next newNode; return newNode; } // 4. 获取尾节点 Node *getTail(Node *head) { Node *p head; while (p-next ! NULL) { p p-next; } return p; } // 5. 判断是否有环核心 int isCycle(Node *head) { Node *fast head; Node *slow head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (fast slow) { return 1; } } return 0; } // 6. 主函数测试 int main() { Node *head initList(); Node *tail getTail(head); // 插入数据1 2 3 4 5 6 7 8 tail insertTail(tail, 1); tail insertTail(tail, 2); tail insertTail(tail, 3); Node *node3 tail; // 保存3号节点 tail insertTail(tail, 4); tail insertTail(tail, 5); tail insertTail(tail, 6); tail insertTail(tail, 7); tail insertTail(tail, 8); // 构造环8 - 3 tail-next node3; // 判断并输出 if (isCycle(head)) { printf(运行结果该链表【有环】\n); } else { printf(运行结果该链表【无环】\n); } return 0; }代码中构造了1→2→3→4→5→6→7→8→3的环形链表isCycle函数检测到快慢指针相遇因此输出有环。五、运行结果编译运行后控制台输出如果你把构造环的代码注释掉// tail-next node3;再次运行结果变为六、总结慢指针 1 步快指针 2 步相遇 有环快指针到 NULL 无环时间复杂度 O (n)空间复杂度 O (1)