141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

哈希表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 非常朴素的哈希表
func hasCycle(head *ListNode) bool {
   hash := make(map[*ListNode]bool)
   for head != nil {
      if _, ok := hash[head]; ok {
         return true
      }
      hash[head] = true
      head = head.Next
   }
   return false
}

快慢指针

fast 每次走两步，slow 每次走一步，若是循环链表一定会相遇

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 非常高级的双指针
func hasCycle2(head *ListNode) bool {
	slow, fast := head, head
	for slow != nil && fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}