快慢指针python

快慢指针，也称为快慢扫描或龟兔赛跑算法，是一种常见的双指针技巧，在Python中常用于解决链表问题，特别是寻找链表中的中间节点或环形链表等问题。两个指针的移动速度不同，通常一个快指针每次移动两步，而另一个慢指针每次移动一步。当链表遍历完整后，由于初始位置的不同，快指针会到达链表的末尾，而慢指针恰好位于链表的中间位置（如果链表是奇数长度）或接近中间位置（如果链表是偶数长度）。

例如，如果你有一个单向链表，你可以使用这个技巧找到链表的中位数，或者确定链表是否有环，并找出环的入口节点。

如果你想要详细了解如何在Python中实现快慢指针，这里是一个简单的例子：

# 假设你有一个链表节点定义如下
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 定义快慢指针
def find_middle_node(head):
    if not head or not head.next:  # 如果链表为空或者只有一个节点，就是中间节点
        return head

    slow = fast = head
    while fast and fast.next:
        slow = slow.next  # 慢指针每次移动一步
        fast = fast.next.next  # 快指针每次移动两步

    return slow  # 返回慢指针指向的节点，即为中间节点