站长工具seo综合查询

发布时间：2025年10月08日作者:zzcha.cn

### 如何判断一个链表是否有环，如何确定入口今天康哥的凉菜鸡offer笔试题，第一个大题就是判断是否有环，然而我忘了，这么经典的题我居然忘了，可能是我最近一直在看前端的题吧，但是面试的时候依然免不了算法数据结构，所以还是要复习的。判断链表是否有环今天康哥的凉菜鸡offer笔试题，第一个大题就是判断是否有环，然而我忘了，这么经典的题我居然忘了，可能是我最近一直在看前端的题吧，但是面试的时候依然免不了算法数据结构，所以还是要复习的。判断链表是否有环，可以用快慢指针的方法，快指针一次走两步，慢指针一次走一步，如果快指针和慢指针相遇，则说明有环。那么问题来了，如何确定入口呢？设链表头到环入口的距离为a，环的长度为b，快指针和慢指针相遇的位置为c，那么有：快指针走的距离：a + k1 * b + c慢指针走的距离：a + k2 * b + c快指针走的距离是慢指针的两倍，所以：a + k1 * b + c = 2 * (a + k2 * b + c)化简得：a = (k1 - 2 * k2) * b - c因为k1和k2都是整数，所以a = k * b - c也就是说，从链表头到环入口的距离等于环长度的整数倍减去相遇点到环入口的距离。所以，当快慢指针相遇时，让一个指针从链表头开始走，另一个指针从相遇点开始走，两个指针每次都走一步，当它们相遇时，就是环的入口。代码实现：class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; }}public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { break; } } if (fast == null || fast.next == null) { return null; } slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }}1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。网友点评