leetcode1

141环形链表

暴力思路：可以直接使用set记录下节点的地址值，如果有重复那么就是有环，如果指针走到了最后那么就说明无环

public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if(!set.contains(head)){
                set.add(head);
            }else
                return true;
            head=head.next;
        }
        return false;
    }

双指针思路:使用快慢指针,如果快指针和慢指针相撞，就说明有环，如果快指针走到头，就说明无环

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;
   }

142环形链表II

与141环形链表1相比,使用set的方法很明显更简单更快捷,而使用双指针则需要一点点数学能力

思路: 假设有环,那么fast一定会走slow的两倍。设slow为k，fast为2k。
我们假设相遇点距离环的起点为m,那么环起点距离头节点为k-m，而在环内的fast走k-m也能到环起点，也就是说当两者相遇的时候k-m就是起点了

图片源自:labuladong.online

双指针解法

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while(fast.next.next!=null&&fast.next!=null){
        slow = slow.next;
        fast=fast.next.next;
        if(fast==slow){
            slow=head;
            break;
        }
    }
    int count =0;
    if(fast==slow){

        while(fast!=slow){
            count++;
            fast=fast.next;
            slow=slow.next;
        }
        return count;
    }
    return null;
}