LeetCode141-环形链表-------剑指Offer022-链表中环的入口

采用快慢指针，fast和slow都从head开始出发，slow每次走一步，fast每次走两步，如果存在环，则一定会相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        
        ListNode fast=head;
        ListNode slow=head;

        while(fast!=null && fast.next!=null){
            
            fast=fast.next.next;
            slow=slow.next;

            if(fast==slow){
                return true;
            }

        }
        return false;

    }
}

如果链表为空返回null。

先通过快慢指针判断是否有环，存在环，则使fast回到头节点，slow留在相遇点，则当速度一致时，再次相遇点就是环的入口，返回即可。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        
        if(head==null || head.next==null){
            return null;
        }

        ListNode fast=head;
        ListNode slow=head;

        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }

        if(fast==null || fast.next==null){
            return null;
        }

        fast=head;

        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }

        return fast;

    }
}