快慢指针

提示

快慢指针是算法中的一种技巧，主要用于处理链表相关的问题。所谓的快慢指针，就是设置两个指针，一个快指针（fast），一个慢指针（slow），它们都从链表的起始位置开始移动。快指针每次移动的步长是慢指针的两倍。通过快慢指针的移动，可以高效地解决链表中的某些问题，比如判断链表是否有环、寻找链表的中点或者倒数第k个元素等。
快慢指针的应用

---

1. 判断链表是否有环

当链表有环时，快慢指针最终会在环内相遇。这是因为快指针每次移动两步，慢指针每次移动一步，如果链表有环，快指针最终会追上慢指针。反之，如果链表无环，快指针最终会到达链表的末尾（遇到null指针）。

提示

分别定义快指针p、慢指针q，初始时两指针均指定链表首结点；快指针每次移动两个结点，慢指针每次移动一个结点；

1. 若链表有环则指针 p、q 一定会相遇（来源数学龟兔赛跑问题），否则快指针为空时返回nullptr；

2. 当p、q 第一次相遇时，假设其相遇于结点I，设结点I距离入口结点G的距离为 d，则此时快指针p移动了 2x = a + d + mR (m为整数)、慢指针q移动了 x = a + d + nR (n为整数)；

3. 易得 a + d = (m - 2n)R；

4. 此时将快指针p重新指向链表首结点，让 p、q 同速运动，则当p再次移动a距离后，p指针移动的距离为 a ，q指针移动的距离为 a + d + nR + a = a + (m - n)R = a + kR (k为整数)；易知此时 p、q 重新相遇且相遇结点即为链表环入口结点；

代码实现：

ListNode *detectCycle(ListNode *head) {
    //先判空
    if (head == nullptr || head->next == nullptr) {
        return nullptr; 
    }
    ListNode *p(head->next->next), *q(head->next);
    while (p != q) {
        if (p == nullptr || p->next == nullptr) {
            return nullptr; // 没有循环
        }
        p = p->next->next;
        q = q->next;
    }

    // 找到循环，将快指针p移到头节点
    p = head;
    while (p != q) {
        p = p->next;
        q = q->next;
    }

    // p和q现在相遇于环的入口
    return p;
}

2. 寻找链表中点

要寻找链表的中点，可以让快慢指针同时从链表头部开始移动，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针将正好位于链表的中点。

3. 寻找链表倒数第k个元素

寻找链表倒数第k个元素时，首先让快指针领先慢指针k-1步，然后快慢指针同时移动。当快指针到达链表末尾时，慢指针将指向链表的倒数第k个元素。