golang力扣leetcode 142.环形链表II

1.设环外链表长为a
2.入环点到相遇点为b
3.相遇到再走回入环点为c
在相遇点
slow走的总距离：a+b
fast走的总路径：a+b+(b+c)n
∵ fast走的路径是slow的两倍
∴ a+b+(b+c)n=2(a+b)
∴ a=(n-1)(b+c)+c
所以相遇点到入环点的距离，加上(n-1)的环长，等于链表头部到入环点的长
这就意味着：链表头和相遇点一起走，他们最终会在入环点相遇

package main
type ListNode struct {
  Val  int
  Next *ListNode
}
//集合
func detectCycle1(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }
  mp := make(map[*ListNode]bool)
  for head != nil {
    if _, ok := mp[head]; !ok {
      mp[head] = true
    } else {
      return head
    }
  }
  return nil
}
func detectCycle2(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }
  fast, slow := head.Next, head
  for fast != nil && fast.Next != nil {
    if fast == slow {
      slow = head
      fast = fast.Next
      for fast != slow {
        fast = fast.Next
        slow = slow.Next
      }
      return fast
    }
    fast = fast.Next.Next
    slow = slow.Next
  }
  return nil
}
func main() {
}