快慢指针的应用

        快慢指针是一种在链表或数组中使用的双指针技巧，通过使用两个指针（快指针（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;
}