要求给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 null。说明不允许修改给定的链表。思路编程思想快慢指针法。快指针每次走两步慢指针每次走一步。如果链表有环两者必然在环内相遇。然后利用相遇点到环入口的距离等于头节点到环入口的距离这一数学关系重新同步遍历找到入口。数学推导设头节点到环入口的距离为 aa环入口到相遇点的距离为 bb相遇点到环入口的距离为 cc环长 LbcLbc。相遇时慢指针走了 abab快指针走了 abkLabkLkk 为快指针在环内绕的圈数且快指针路程是慢指针的2倍即2(ab)abkL ⟹ abkL ⟹ akL−b(k−1)Lc2(ab)abkL⟹abkL⟹akL−b(k−1)Lc当 k1k1 时acac。即从头节点到入口的距离等于相遇点到入口的距离沿着环走。因此将其中一个指针放回头节点两者同步每次一步再次相遇处即为环入口。题解publicListNodedetectCycle(ListNodehead){if(headnull||head.nextnull){returnnull;}ListNodefasthead;ListNodeslowhead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(slowfast){break;}}if(fastnull||fast.nextnull){returnnull;}slowhead;while(slow!fast){slowslow.next;fastfast.next;}returnfast;}注意一定要注意对边界条件的判断要想保证快指针能够安全地移动两步就必须保证fast ! null fast.next ! null。如果链表有环则循环能够一直进行直到快慢指针相遇执行break退出循环。如果链表无环则快指针要么走到链表的最后一个节点要么走到最后一个节点后面的null这两种情况都会自动退出循环。