题解 | #链表中环的入口结点#

简单思路：使用哈希表

package main

func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    if pHead==nil{
        return nil
    }
    mp:=make(map[*ListNode]struct{})
    p:=pHead
    for p!=nil{
        if _,ok:=mp[p];ok{
            return p
        }else{
            mp[p]=struct{}{}
        }
        p=p.Next
    }
    return nil
}

使用快慢指针，难点在于数学推理出如何走才能在环开头除碰面。

• 推理过程

因此找到相遇点后，只需要q指针从头开始遍历，s指针从相遇点开始遍历，下一次相遇点就是环的起始点。

package main

func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    if pHead==nil{
        return nil
    }
    q:=pHead
    s:=pHead
    for q!=nil&&q.Next!=nil{
        q=q.Next.Next
        s=s.Next
        if q==s{
            break
        }
    }
    if q==nil||q.Next==nil{
        return nil
    }
    q=pHead
    for q!=s{
        q=q.Next
        s=s.Next
    }
    return q
}