目录
官网地址：https://www.dhcode.cn/p/t_pc/goods_pc_detail/goods_detail/term_624bd804b3d39_Ac0g7V?fromH5=true&type=3&channel_id=&pro_id=term_624bd804b3d39_Ac0g7V
本内容大部分从中截图
讲了三个力扣题：876，142
快慢指针
快慢指针，也被称为龟兔赛跑算法，是一种在计算机科学中用于检测链表中是否存在环的算法。这个算法的灵感来源于伊索寓言中的龟兔赛跑故事，其中慢的指针（龟）和快的指针（兔）同时开始移动，但快的指针移动得更快。
算法步骤：
-
初始化：设置两个指针
slow和fast，它们都指向链表的头节点head。 -
移动指针：在每次迭代中，
slow指针向前移动一步（即slow = slow.next），而fast指针向前移动两步（即fast = fast.next.next）。 -
检测相遇：如果链表中存在环，
fast指针和slow指针最终会在环内的某个点相遇。如果fast指针或fast.next为None（即到达了链表的末尾），则链表中不存在环。 -
确定环的入口（如果存在环）：一旦
slow和fast相遇，可以通过以下步骤找到环的入口：- 将
slow重置为链表的头节点head。 - 同时移动
slow和fast指针，每次只向前移动一步，直到它们再次相遇。 - 当它们再次相遇时，这个点就是环的入口。
- 将
为什么有效？
- 不同速度：快慢指针以不同的速度移动，如果存在环，快指针最终会追上慢指针。
- 节省时间：相比于遍历每个节点并记录它们（这需要额外的存储空间），快慢指针算法只需要常数级的存储空间，并且时间复杂度为 O(n)，其中 n 是链表中节点的数量。
使用场景：
快慢指针算法主要用于检测链表中的环，例如在以下场景中：
- 检测单向链表或双向链表中是否存在环。
- 确定环的长度（通过在相遇后继续移动一个指针直到再次相遇）。
快慢指针是一种非常高效且节省空间的解决方案，适用于链表环检测问题。
力扣876
题目
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。提示：
- 链表的结点数范围是 [1, 100]
- 1 <= Node.val <= 100
方法
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow= head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow力扣142
题目
给定一个链表的头节点 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) 空间解决此题？
方法1
代码
方法2
思路
代码
# 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]:
fast = head
slow =head
meet =None
while fast and fast.next:
fast =fast.next.next
slow = slow.next
if fast == slow:
meet = fast
break
while head and meet and head != meet:
head = head.next
meet = meet.next
return meet