快慢指针的应用

        快慢指针是一种在链表或数组中使用的双指针技巧，通过使用两个指针（快指针（fast）和慢指针（slow））以不同的速度遍历数据结构，从而高效地解决一些特定问题。

链表相关问题：

1.链表的中间结点

快指针(fast):每次走两步

慢指针(slow):每次走一步

下面，我们将分别对链表数据个数为奇数和偶数这两种情况展开详细分析。

单数：

在链表数据个数为奇数的情形下，当快指针（fast）行进至链表的最后一个结点时，慢指针（slow）恰好停留在链表的中间结点处。

双数

在链表数据个数为偶数的情况下，当快指针（`fast`）移动到 `NULL` 位置时，慢指针（`slow`）刚好抵达链表两个中间结点中的第二个结点处

那么我们由此看出当快指针(fast)走到最后一个结点，或者时最后一个结点的下一位是得到链表的中间结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

2.寻找链表中的倒数第K个节点

思路：

我们知道，倒数第 k 个节点与链表最后一个节点之间间隔的节点数为 k - 1。基于此特性，我们可以采用双指针法来解决该问题。

具体操作如下：

首先，对快指针和慢指针进行初始化，让快指针先向前移动 k - 1 步。这样一来，快指针和慢指针之间的距离就恰好为 k - 1 个节点。

随后，在后续的移动过程中，让快指针和慢指针以相同的速度同步向前移动。由于它们始终保持着 k - 1 个节点的距离，那么当快指针移动到链表的最后一个节点时，慢指针所在的位置就是链表的倒数第 k 个节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* fast,*slow;
    fast=slow=head;
    while(k--)
    {
        fast=fast->next;
    }

    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }

    return slow->val;
}

3.判断链表是否有环

在学术领域，我们通常将其称为Floyd判圈算法，也叫龟兔赛跑算法，不过其核心思想本质上就是快慢指针思想。倘若链表中存在环，那么快指针（fast）和慢指针（slow）必然会在某次循环过程中相遇。这背后的原理是什么呢？

我们通过图来理解一下：

情况一：fast落后slow一步：

在下次移动时fast移动两步，slow移动一步，这是fast和slow相遇，判定此链表有环

fast落后slow两步：

以此类推，当快指针（fast）落后慢指针（slow）三步时，经过一次移动就会回到之前所讨论的情况二；再移动一次，便回到情况一；接着再移动一次，快指针与慢指针就会相遇。由此我们可以推断，无论快指针最初落后慢指针多少步，经过若干次循环（循环次数为二者初始步数差减 1），快指针和慢指针最终都会相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while(slow && fast && fast -> next)
    {
        fast = fast -> next -> next;
        slow = slow -> next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

4.寻找环形链表的入环点

这里推荐大家看代码随想录的分享

代码随想录

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast,*slow;
    fast=slow=head;
    //找出相遇点
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {//相交，找环形入口；分别从头部和从交点出发，找到相遇的点就是环形入口
            struct ListNode* index1=fast;
            struct ListNode* index2=head;
        
        while(index1!=index2)
        {
            index1=index1->next;
            index2=index2->next;
        }
        return index1;
        }
    }
    return NULL;
}