【leetcode】142.（Medium）Linked List Cycle II

解题思路：

第一种做法：维护一个map
第二种做法：双指针（做法来自题目后面讨论区）

提交代码：维护map

class Solution {
	public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)	return null;
        
        Map<ListNode,Boolean> map=new HashMap<>();
        ListNode p=head;
        while(p!=null) {
        	if(map.containsKey(p))	return p;
        	map.put(p, true);
        	p=p.next;
        }
        return null;
    }
}

运行结果：

提交代码：双指针

class Solution{
	public ListNode detectCycle(ListNode head) {
		if(head==null||head.next==null)	return null;
		
		ListNode p1=head.next,p2=head.next.next;
		while(p1!=p2) {
			p1=p1.next;
            if(p2!=null&&p2.next!=null&&p2.next.next!=null)
			    p2=p2.next.next;
            else return null;
		}
		p1=head;
		while(p1!=p2) {
			p1=p1.next;
			p2=p2.next;
		}
		return p1;
	}
}

运行结果：