Linked List Cycle

题目描述

环形链表

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

示例：

输入：head = [3, 2, 0, -4], pos = 1, pos表示链接到链表中的位置
输出：true
解释：链表中有一个环

输入：head = [1], pos = -1
输出：false
解释：链表中没有环

解法

方法一：利用哈希表

每遍历一个节点，就从哈希表中检查是否存在该指针，如果存在则表示有环。如果不存在，则将该节点添加到哈希表。直到遍历结束。

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func hasCycle(head *ListNode) bool {
    nodeM := make(map[*ListNode]int)

    for head != nil {
        if _, ok := nodeM[head]; ok {
            return true
        }
        nodeM[head] = 1
        head = head.Next
    }
    return false
}

方法二：快慢指针

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func hasCycle(head *ListNode) bool {
    stepOne := head
    stepTwo := head

    for stepTwo != nil && stepTwo.Next != nil {
        stepOne = stepOne.Next
        stepTwo = stepTwo.Next.Next

        if stepOne == stepTwo {
            return true
        }
    }

    return false
}