力扣日刷251120

今天跟女朋友打了一会三角洲，现在才开始做题，争取也完成3道以上吧哈哈哈哈

第一题：

这一题，我先看了题解，题解中暴力求解的办法就是把每次遇到的指针（head）都加入到一个set()当中，然后循环体head，当head非空时，进行一个判断，如果head在set中出现过就回Ture，反之就False。下面是官方题解：

1class Solution:
2    def hasCycle(self, head: ListNode) -> bool:
3        seen = set()
4        while head:
5            if head in seen:
6                return True
7            seen.add(head)
8            head = head.next
9        return False
10

我基于官方题解进行了复现，但是也还是有点不一样：我加多了一个逻辑更复杂了一点。还是官方比较清楚。

1class Solution:
2    def hasCycle(self, head: Optional[ListNode]) -> bool:
3        seen = set()
4        while head not in seen and head !=None:
5            seen.add(head)
6            head = head.next
7        if head in seen:
8            return True
9        return False
10

这一题还有一种解法，因为下面第二题要用到，这里就提前说了：用快慢指针的方法去解决：如果有环，慢指针总会有被快指针套圈的时候，这时候就可以判断了！

1class Solution:
2    def hasCycle(self, head: Optional[ListNode]) -> bool:
3        show = fast = head
4        while fast and fast.next:
5            show = show.next
6            fast = fast.next.next
7            if show ==fast:
8                return True
9        return False
10

第二题：

这一题是一个数学题：其主要核心的思想就是当慢指针与快指针相遇时，head指针开始走第一次会在环的开始节点相遇。具体的东西建议看灵神的视频：https://www.bilibili.com/video/BV1KG4y1G7cu/?vd%5Fsource=5be82feb0bc67fab83245df3d321eb87

下面是灵神的题解，我的题解仿照灵神，所以就不再拿出来看了！

1class Solution:
2    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        slow = fast = head
4        while fast and fast.next:
5            slow = slow.next
6            fast = fast.next.next
7            if fast is slow:  # 相遇
8                while slow is not head:  # 再走 a 步
9                    slow = slow.next
10                    head = head.next
11                return slow
12        return None
13

但是这里有一点需要注意的就是：两个return的位置，外面的return是在循环之外的，内部是在循环里面的但在show与head循环判断之外！

今天困了写了一个小时，明天补回来吧！

《力扣日刷251120》是转载文章，点击查看原文。