1、判断有环
二指针,一个一次走一步,一个一次走两步。出现相遇点则有环
func hasCycle(head *Node) (meet *Node bool) {
if head == nil || head.next == nil {
return head, false
}
slow := head
fast := head
for fast != nil && fast.nextNode != nil {
slow = slow.nextNode
fast = fast.nextNode.nextNode
if fast == slow {
return slow, true
}
}
return head, false
}
2、找到环起点
从相遇节点往下走到环的开始节点的距离和从head节点到环的开始节点的距离相等