Force buckle 142 Circular linked list II

subject ：

Ideas ：

        Judge whether the linked list is linked , You can use the speed pointer , If the pointer traverses to null, It will not form a ring , If the two overlap , Then form a ring , There are two ways to judge the entry point ,1 When overlapping , Add a new one from head Start node , With overlapping points next, The next overlapping point is the entry point ,2 Yes, it is hash Mark the place where the fast pointer has passed .

Code ：

Hash + Speed pointer ：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashMap<ListNode,Integer> hash=new HashMap<ListNode,Integer>();
        ListNode l1=head;
        ListNode l2=head;
        while(l2!=null){
            if(hash.containsKey(l2)){
                return l2;
            }else{
                hash.put(l2,0);
            }
            l1=l1.next;
            l2=l2.next;
            if(l2==null){
                return null;
            }else{
                if(hash.containsKey(l2)){
                    return l2;
                }else{
                    hash.put(l2,0);
                }
                l2=l2.next;
            }
        }
        return null;
    }
}

Three pointers

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode l1=head;
        ListNode l2=head;
        while(l2!=null){
            l1=l1.next;
            l2=l2.next;
            if(l2==null){
                return null;
            }else{
                l2=l2.next;
                if(l2==l1){
                    ListNode l3=head;
                    while(l3!=l1){
                        l1=l1.next;
                        l3=l3.next;
                    }
                    return l3;
                }
            }
        }
        return null;
    }
}