142.环形链表

一、问题描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

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

进阶：

• 你是否可以不用额外空间解决此题？

二、方案一：哈希表法

1、思路

遍历链表，对于每个节点，检查它是否在哈希表中。如果在，则该节点是环的入口；如果不在，则将其添加到哈希表中。

2、代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    nodes := map[*ListNode]bool{}
    for node := head; node != nil; node = node.Next {
        if nodes[node] {
            return node
        }
        nodes[node] = true
    }
    return nil
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的节点数。
• 空间复杂度：O(n)，需要存储每个节点的引用。

三、方案二：快慢指针法

1、思路

使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。如果链表中存在环，则快慢指针最终会在环内相遇。然后，将一个指针重新设置到链表头部，另一个指针保持在相遇点。两个指针以相同速度移动，它们将在环的入口相遇。

2、代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    // 初始化快慢指针，都从链表头部开始
    slow, fast := head, head

    // 快指针每次移动两步，慢指针每次移动一步
    for fast != nil && fast.Next != nil {
        slow = slow.Next           // 慢指针移动一步
        fast = fast.Next.Next      // 快指针移动两步

        // 如果快慢指针相遇，说明链表中有环
        if slow == fast {
            // 将一个指针重新设置到链表头部
            slow = head
            // 两个指针以相同速度移动，它们将在环的入口相遇
            for slow != fast {
                slow = slow.Next  // 慢指针移动一步
                fast = fast.Next  // 快指针移动一步
            }
            // 返回环的入口节点
            return slow
        }
    }
    // 如果快指针到达链表尾部，说明链表中没有环
    return nil
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的节点数。
• 空间复杂度：O(1)，不需要额外的空间。

四、总结

方案	时间复杂度	空间复杂度	备注
哈希表法	O(n)	O(n)	需要额外的空间存储节点
快慢指针法	O(n)	O(1)	不需要额外空间

快慢指针法在空间复杂度上优于哈希表法，因为它不需要额外的空间来存储节点。在实际应用中，如果对空间复杂度有要求，通常更倾向于使用快慢指针法。