| 来源：学益得智能硬件 |2023-08-10 17:39:22 |
(资料图)
如何判断链表是否有环？首先，有环的链表应该长这样。 正常的单向链表最后一个结点的指针域应该是NULL，表示后面没有结点。 但是如果把它改成前面某个结点的地址，就会变成这个样子，这样的链表就叫有环的链表。 如何判断链表是否有环，其中一个比较常见的方法就是，两个指针，经常把他们称作快慢指针，慢的指针每次走一步，快的指针每次走两步，如果链表没环，快的指针肯定最先达到终点；如果链表有环，那么两个指针迟早相遇。 代码也极其简单：
int is_cross(Node *head){ if (NULL == head) return 0; Node *fast = head; Node *slow = head; while (fast && slow) { if (fast->next && fast->next->next) fast = fast->next->next; else break; if (slow->next) slow = slow->next; else break; if (fast == slow) return 1; } return 0;}很经典的面试题，不过一般面试官还会继续问，如何找出环开始的结点，这里就会涉及到一点数学问题。我直接来说步骤。 当快指针和慢指针相遇的时候，再定义一个指针指开头。该指针和慢指针同时向后走。两个指针相遇的时候，就是环开始的结点。
int is_cross(Node *head){ if (NULL == head) return 0; Node *fast = head; Node *slow = head; while (fast && slow) { if (fast->next && fast->next->next) fast = fast->next->next; else break; if (slow->next) slow = slow->next; else break; if (fast == slow) { Node *p = head; while (p != slow) { p = p->next; slow = slow->next; if (p == slow) { /*环开始的结点*/ } } } } return 0;}审核编辑：汤梓红
责任编辑：【henankuaibao】
关键词：
![瑶的真我赫兹皮肤多少钱 王者瑶真我赫兹皮肤价格分享[多图]](http://img.kjw.cc/2022/0923/20220923103200742.jpg)
