检测一个单链表是否有环？

问题

单链表有环，指的是单链表中有某个节点的 next 指向的事前面的某个节点，这样在单链表的尾部就形成了一个环形结构。如何判断单链表是否有环存在？

解法

先预定义好单链表

type LNode struct {
	Data int
	Next *LNode
}

func NewLList() *LNode {
	return &LNode{}
}

用 set/map 存储并检测

思路很简单，即遍历单链表，将遍历到的节点索引记录到 set/map 中，遍历下一个节点时检测当前节点是否在 set/map 中存在，存在的话则有环存在。

Go 中无 set，就用 map 代替：

func checkRing(head *LNode) bool {
    if head == nil || head.Next == nil {
		return false
	}
	tmp := make(map[*LNode]interface{})
	node := head
	for node.Next != nil {
		if _, ok := tmp[node]; ok {
            // 遍历到的节点之前遍历过
			return true
		}
        // 将遍历过的记录下来
		tmp[node] = nil
        // 向后移动
		node = node.Next
	}
	return false
}

func main() {
	// 创建示例数据
	node1 := &LNode{Data: 1}
	node2 := &LNode{Data: 2}
	node3 := &LNode{Data: 3}
	node4 := &LNode{Data: 4}
	node5 := &LNode{Data: 5}

	l := NewLList()
	l.Next = node1
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5

	exists := checkRing(l)
    // 是否有环？ false
	fmt.Println("是否有环？", exists)

	node5.Next = node3

	exists = checkRing(l)
    // 是否有环？ true
	fmt.Println("是否有环？", exists)
}

这种方法时间复杂度为 O(n)，空间复杂度为 O(n)。

快慢指针

思路是用两个快慢指针从头开始走，一快一慢。慢指针一次走一步，快指针一次走两步，如果单链表有环的话，那么快指针肯定与慢指针相遇。

这相遇情况就像两个人在操场按同一个方向跑步，快的人肯定能在后面追上慢的人。

func checkRing2(head *LNode) bool {
	if head == nil || head.Next == nil {
		return false
	}

	slow := head.Next
	fast := head.Next

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
            // fast 追上了 slow
			return true
		}
	}
	return false
}

func main() {

	// 创建示例数据
	node1 := &LNode{Data: 1}
	node2 := &LNode{Data: 2}
	node3 := &LNode{Data: 3}
	node4 := &LNode{Data: 4}
	node5 := &LNode{Data: 5}

	l := NewLList()
	l.Next = node1
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5

	exists := checkRing(l)
    // 是否有环？ false
	fmt.Println("是否有环？", exists)

	node5.Next = node3

	exists = checkRing(l)
    // 是否有环？ true
	fmt.Println("是否有环？", exists)
}

时间复杂度为 O(n)，空间复杂度为 O(1)。