题目
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：

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

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 104]
- -105 <= Node.val <= 105
- pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
我的代码（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:
if not head or not head.next:
return False
myNode = ListNode(0)
tmp0 = head
tmp1 = head.next
while tmp0 != None and tmp0 != myNode:
tmp0.next = myNode
tmp0 = tmp1
tmp1 = tmp1.next if tmp1 else None
return tmp0 == myNode点评
最直观的做法，是哈希，把遍历过的结点存储起来，保证O(1)的插入和查询的时间复杂度，然后当遍历到已经存储过的结点时，就知道遇到环了。
官方的优化做法，是快慢指针。看来在链表问题上，快慢指针是很常见的做法。
不过我保留了我的做法：每遍历一个结点，就把这个结点的next指向我预设好的一个结点。这样当遇到新的结点，next指向这个预设结点时，就说明遇到环了。
当然这个做法不好，虽然官方没有指明需要保证链表结构，解答也被接受了，但是像我这样直接把整个链表都拆了，在实际工程中恐怕会出问题。
不过还是挺好玩的～😄
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog