给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
题解:
- 快慢指针法,快指针一次走两步,慢指针一次走一步,当快慢指针第一次相遇,此时: 2(x+y)=n圈周长+x+y
- 相遇以后快指针回到head和慢指针以同样速度每次走一步,最终会在链表中环的入口结点处相遇。
这里可以这样理解, x + y = n圈周长, y = n圈周长 - x; 快慢指针再继续走x后, 快指针走到入口点,此时慢指针再圆中走的路程为: x + y, 刚好为圆n圈周长。
package com.alibaba.study.tiba;
import com.alibaba.fastjson.JSON;
import com.alibaba.study.utils.ListNode;
/**
* @Auther: wjj
* @Date: 2021/1/12 16:06
* @Description:
*/
public class LeetCode142 {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null || head.next.next ==null){
return null;
}
ListNode slow = head;
ListNode fast = head.next.next;
while (slow != fast){
if(slow == null || fast == null || fast.next == null){
return null;
}
slow = slow.next;
fast = fast.next.next;
}
fast = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}