环形链表

1. 题目描述

给定一个链表，判断链表中是否有环。

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

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

2. 思路

1. 思路一
   • 使用set记录走过的节点
   • 如果下一个节点在set中，说明是环节点，返回之
2. 思路二
   • 快慢指针
   • 快指针走两步，慢指针走一步
   • 注意两指针虽然相遇，但是相遇的节点却可能不是环的入口节点

3. 实现

3.1. map

func hasCycle2(head *ListNode) bool {
	count := make(map[*ListNode]bool, 0)
	current := head
	for current != nil {
		if count[current] {
			return true
		}
		count[current] = true
		current = current.Next
	}

	return false
}

3.2. 快慢指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {

        fast = fast.Next.Next
        slow = slow.Next
        //这个放在修改指针的后面，放在前面则需求加上!=head
        if fast == slow {
            return true
        }
    }

    return false
}

4. 参考

• 141. 环形链表 - 力扣（LeetCode）
• 链表中环的入口结点.md