46.Linked List Cycle-环形链表

题目描述：


解析：快慢指针，慢指针一次走一步，快指针一次走两步，如果重合，必有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        //快慢指针
        if (head==null) return false;
        ListNode p1=head;
        ListNode p2=head;
        while(p1!=null && p2!=null && p2.next!=null) {  
            p1=p1.next;  
            p2=p2.next.next;
            if(p1==p2) return true;
        }
        return false;
    }
}

如果要找到入环的第一个节点，则需要有一个指针返回链表头节点，然后两个指针都是一次走一步，再次重合就是入环的首节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null) return null;
        ListNode p1=head;
        ListNode p2=head;
        while(p1!=null && p2!=null && p2.next!=null){
            p1=p1.next;
            p2=p2.next.next;
            if(p1==p2) { //说明有环
                p1=head;  //重新指向链表头节点
                while(p1!=p2){  //直到p1==p2的时候
                    p1=p1.next;
                    p2=p2.next;
                }
                return p1;
            }
        }
        return null;
    }
}