快慢指针（有趣的算法讲解）

简介（来源于科大讯飞）

快慢指针是一种在数据结构中用于解决特定问题的有效技巧，特别是在链表和数组中寻找循环或中点等场景中应用广泛。

快慢指针通常涉及两个指针以不同的速度移动。一般情况下，慢指针每次移动一步，而快指针每次移动两步。这种方法可以快速判断链表中是否存在循环，或者有效地找到链表的中点，而无需额外的存储空间。

快慢指针的概念和应用都比较简单，但它在解决一些复杂问题时展现出了高效和巧妙的一面。在链表或数组中寻找重复的数字、检测链表中的循环、查找链表的中点等问题中，快慢指针都表现出了其独特的优势。

在使用快慢指针进行链表环检测时，如果快指针赶上了慢指针，则表明链表中存在环；如果快指针到达了链表的尾部，则说明链表无环。这一方法的时间复杂度为O(n)，空间复杂度为O(1)，是一种非常高效的解决方案。

此外，快慢指针还可以用来找出链表的中点，将链表分为两个部分，这对于链表的归并排序等操作非常有帮助。快慢指针在此场景下的应用也具有时间复杂度为O(n)和空间复杂度为O(1)的优势。

总的来说，快慢指针作为一种简单但强大的技术，其在数据结构中的应用十分广泛，并且能够高效解决一类可以通过迭代来解决的问题。理解并掌握快慢指针的使用，对提升解决实际问题的能力大有裨益。

大白话讲算法

快慢指针，从字面上看，就是两个指针以快慢不同的速度移动。简单地说，就像散步时你是一个慢指针，而跑步时则变成了快指针。这样的理解是不是非常直观？虽然快慢指针的概念本身很简单，但将其灵活应用到实际问题中才是真正的挑战！

漫画展示流程

现在将快慢指针想象为两颗火箭。

想象这样一个场景：一个人向两颗火箭提出问题，询问它们是否知道地球的形状。两颗火箭都摇头表示不清楚。这时，那人不禁叹息，表达了自己强烈的好奇心，想知道地球究竟是什么形状。就在此时，一只蓝色的狸猫出现了，它自信地宣称：“我能告诉你们地球的样子，但需要你们两颗火箭，快与慢的配合。”

于是，快慢火箭带着满满的信心，踏上了漫长而充满未知的冒险之旅。

快火箭的速度极其惊人，仅仅一天就与慢火箭拉开了巨大的距离。令人惊讶的是，仅仅过了三天，快火箭就再次遇见了那只蓝色的狸猫。

蓝色狸猫对快火箭说：“根据我的计算，你只要继续以当前的速度飞行，到了第六天，就能与慢火箭在这里会合。所以，继续往前飞吧！”

当两颗火箭最终再次相遇时，蓝色的狸猫问道：“你们现在知道地球是什么形状了吗？”快火箭和慢火箭，以及最初提出问题的那个人，异口同声地回答：“地球是一个巨大的环。”蓝色的狸猫听后露出了笑容，并恭喜他们答对了！

具体实例

环形链表

给你一个链表的头节点 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 或者链表中的一个 有效索引 。

实现代码如下

# 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:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False

链表的中间结点

给你单链表的头结点 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]:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow