Leetcode-141.环形链表

Leetcode
1.2k 词

dict和set

1. 结构上的区别：

类型 键（Key） 值（Value） 示例
dict 有 有 {'a': 1, 'b': 2}
set 有 没有 {'a', 'b'}

  • dict 是**键值对（key-value）**的集合。

  • set 是只有键（key）没有值的一组唯一元素。

2. 用途上的区别：

  • dict 用于建立键与值的映射，例如地址到位置、用户名到ID等。

  • set 用于快速查找是否存在、去重、集合运算等，例如判断某个元素是否出现过。

3. 操作上的区别：

dict 常见操作：

1
2
3
4
d = {'x': 1, 'y': 2}
d['z'] = 3             # 添加键值对
value = d.get('x')     # 查找键对应的值
del d['y']             # 删除键值对

set 常见操作：

1
2
3
4
s = {'a', 'b'}
s.add('c')             # 添加元素
s.remove('a')          # 删除元素
exists = 'b' in s      # 判断是否存在

4. 底层实现的共同点和不同点：

  • 相同点：都使用哈希表，所以查找、插入、删除的时间复杂度平均为 O(1)O(1)。

  • 不同点：

    • dict 哈希表存储的是 (key, value) 对，插入更复杂。

    • set 只存 key，没有 value，占用空间略小，操作略快。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

```python
# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None
class Solution:

    def hasCycle(self, head: Optional[ListNode]) -> bool:

        seen=set()

        while head:

            if head in seen:

                return True

            seen.add(head)

            head=head.next

        return False

思路：

利用集合 seen 记录遍历过程中出现过的节点引用（即内存地址）。若遍历某个节点时发现它已经在 seen 中，说明这个节点之前已经访问过，即链表存在环。否则，将当前节点加入集合并继续向后遍历。

🧠解题过程：

  1. 创建一个空集合 seen；

  2. 从头节点 head 开始，逐个遍历每个节点；

  3. 如果当前节点 head 已存在于 seen 中，说明链表出现了环，返回 True；

  4. 否则将当前节点加入集合，继续向下一个节点遍历；

  5. 若遍历到 None，说明链表无环，返回 False。