做数学题网站,在线图片处理工具,江西学校网站建设,江干区住房和城市建设局网站力扣题目链接
思路#xff1a;判断链表是否有环#xff1f;可以使用快慢指针法#xff0c;快指针每次走两步#xff0c;慢指针每次走一步#xff0c;如果链表有环一定会在环中相遇。
如何找环的入口#xff1f;当快慢指针在环中第一次相遇时#xff0c;让快指针从头结…力扣题目链接
思路判断链表是否有环可以使用快慢指针法快指针每次走两步慢指针每次走一步如果链表有环一定会在环中相遇。
如何找环的入口当快慢指针在环中第一次相遇时让快指针从头结点出发慢指针从相遇节点出发每次都走一步两指针再次相遇时即为环的入口。 假设快慢指针相遇时快指针只在环中走了一圈。当慢指针走到b点时此时快指针走到c’点由于快指针走的步数是慢指针的两倍当慢指针走x步到b时快指针就会走2*x步到c’因此可得b-c’的长度为x。快慢指针会在c点相遇显然c-b的长度也为x。因此如果慢指针从相遇点c出发快指针从a点出发两个指针每次都走一步一定会在环形入口b点相遇的。
代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head, slow head;while (true) {if (fast null ||fast.next null) return null;fast fast.next.next;slow slow.next;if (fast slow) break;}fast head;while (fast ! slow) {fast fast.next;slow slow.next;}return fast;}
}
