题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：- 链表中节点的数目范围在范围 [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 detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
slowIdx, fastIdx = head, head.next
slowCnt, fastCnt, circleLen = 0, 0, 0
while slowIdx and fastIdx:
if fastIdx == slowIdx:
circleLen = fastCnt - slowCnt + 1
break
elif fastIdx.next == slowIdx:
circleLen = fastCnt - slowCnt + 2
break
slowIdx = slowIdx.next
slowCnt += 1
fastIdx = fastIdx.next.next if fastIdx.next else None
fastCnt += 2
print(f'circleLen: {circleLen}')
if not fastIdx:
return None
slowIdx, fastIdx = head, head.next
cnt = 1
while slowIdx != fastIdx:
fastIdx = fastIdx.next
cnt += 1
if cnt > circleLen:
slowIdx = slowIdx.next
return slowIdx点评
这次是想到了快慢指针，不过效率还是不好。
我的想法是根据快慢指针相遇的步数算出这个链表中的环的长度l，然后再用两个指针，一个在Head，另一个在l处同步向后查找，这样当两者相遇时就是环的第一个结点。
结果是对的，时间效率、空间效率也都满足，但是遍历次数还是太多。
官方比我少遍历一次。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog