23 链表中环的入口结点

牛客

描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

可以使用 HashSet 来储存遍历过的节点，如果访问到遍历过的节点，则该节点为环的入口处。空间复杂度 o(n)，时间复杂度 o(n)

public ListNode EntryNodeOfLoop(ListNode pHead) {
    HashSet<ListNode> set=new HashSet<>();
    while(pHead!=null && !set.contains(pHead)){
        set.add(pHead);
        pHead = pHead.next;
    }
    return pHead;
}

可以定义一个方法判断环的节点个数 count ，然后第 1 个指针每次移动 count 步（转一圈），第 2 个指针每次移动 1 步，如果，如果第二个指针到达环的入口，肯定会在第 1 个指针转圈时相遇。空间复杂度 o(1)，时间复杂度 o(n²)，虽然表面上时间复杂度高，实际上移动指针挺快的。

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        int count = count(pHead);
        if(count==-1) return null;
        ListNode p1=pHead, p2=pHead;
        while(true){
            for(int i=0;i<count;++i){
                p1 = p1.next;
                if(p1==p2) return p1;
            }
            p2 = p2.next;
        }
    }
    
    private int count(ListNode pHead){
        ListNode p1=pHead, p2=pHead;
        while(p1!=null && p1.next!=null){
            p1 = p1.next.next;
            p2 = p2.next;
            if(p1==p2){
                int count = 0;
                while(true){
                    p1 = p1.next;
                    ++count;
                    if(p1 == p2) return count;
                }
            }
        }
        return -1;
    } 
}