很多同学都听过快慢指针这个名词，认为它不就是定义两个引用（指针）一前一后吗？是的，它的奥秘很深，它的作用究竟有哪些？究竟可以用来做哪些题目？下面我将一一带你了解和应用
下面的本节的大概内容，有疑惑的点，欢迎小伙伴们留言
目录
1.简述快慢指针
2.快慢指针实战讲解
1.求链表的中间结点
2.链表中倒数第k个结点
3.删除排序链表中的所有重复元素
3.题型于快慢指针的小总结
1.简述快慢指针
（1）快慢指针只是一种说法，不是直接定义两个指针；在Java中就没有指针这个概念
（2）快慢指针定义两个引用，一般慢指针定义为slow，快指针定义为fast
（3）快慢指针常见的思想：
1.一般快指针所指向的对象需要满足某个条件，慢指针才能继续向前走
2.快慢指针一起走，但是每次快指针走的距离都比慢指针多
3.快指针先走n步，然后快慢指针再一起走
（4）常应用于数组和链表中
2.快慢指针实战讲解
下面带你一步一步学会快慢指针在链表中的应用，它是怎么运用的和应用
1.求链表的中间结点
（1）这是一道leetcode上面的题目，下面附上链接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
不想点进去的同学也不要慌张，下面我展示题目：
（2）理解题目
第一、这是单链表的题目
第二、本题给的例子有两个：第一个是结点数是奇数的时候，第二个是结点数是偶数的时候，用数学公式表示就是：中间结点=结点个数/2（规定第一个结点下标为0）
第三、题目要求：找到中间的结点，并返回中间结点
下面讲解这种题的解法
（3）暴力解法（不推荐）
很多同学是这么想的，要求中间结点，首先要知道中间结点的位置不就好了；然后先遍历一遍链表，记下结点的个数，算出中间结点的位置；再遍历第二遍，遍历到中间位置就停下。
缺点：缺点很明显，时间复杂度太大，如果题目要求时间复杂度为O(n)，也就是只遍历一遍链表，就找出中间结点，同学该如何应对。
下面介绍本节的重点算法思想：快慢指针
（4）利用快慢指针巧解（重点）
我们再看一下题目：下面分为五步去讲解
第一步：定义两个引用指向头结点
ListNode slow = head;//慢指针
ListNode fast = head;//快指针第二步：怎么操作？
我们规定每次，快指针走两步，慢指针走一步，当快指针停下来的时候，慢指针指向的结点就是中间结点
原理剖析：
第三步：代码演示
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}第四步：快指针走完的判断条件
fast != null && fast.next != null看条件有两种，就是对应结点数是奇数或偶数的情况
奇数（条件一：fast.next != null）
偶数（条件二：fast != null）
第五步：判断特殊情况
当一个头结点都没有的时候，也就是head==null，那还找个鸡毛，直接返回就好
if(head == null) {
return null;
} 完整代码：
public ListNode middleNode(ListNode head) {
if(head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
可见，使用快慢指针的效率是多么的快
2.链表中倒数第k个结点
（1）这是一道牛客网上面的题目，下面附上链接
链表中倒数第k个结点_牛客题霸_牛客网
下面附上题目：
（2）理解题目
第一、要求我们返回倒数某个结点，最后一个标号为倒数第一；
第二、题目在时间和空间上面都有限制，并且知识点里面有双指针的标签
（3）暴力求解（不推荐）
依旧是同样的套路，先遍历一遍链表，记录下结点的总数；利用结点总数-倒数某个结点，再遍历第二次链表就可以知道遍历到哪个位置便利用停下来。
这种方法的时间限制可能会超出题目的要求，也是不推荐的，下面介绍快慢指针的解法
（4）快慢指针思想（重点推荐）
第一步：定义一个fast和slow的引用，开始都指向头节点。
ListNode slow = head;
ListNode fast = head;第二步：求倒数第K个结点，那就先让快指针（fast）先走（k-1）步
int count = k-1;//走k-1步
while(count > 0) {
if(fast.next!=null) {
fast = fast.next;
count--;
}else {
return null;
}
}第三步：fast走完k-1步后，fast和slow一起走，当fast停下的时候，slow的位置就是所求的结点位置
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}原理及终止条件：
特殊情况的考虑：
第四步：特殊情况考虑
当头结点为空时，也就是一个结点都没有的时候，直接返回null
if(head == null) {
return null;
}当k的取值不合法时，比如是非正数，直接返回就好
if(k<=0) {
return null;
}完整代码：
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null) {
return null;
}
if(k<=0) {
return null;
}
ListNode slow = head;
ListNode fast = head;
int count = k-1;
while(count > 0) {
if(fast.next!=null) {
fast = fast.next;
count--;
}else {
return null;
}
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
3.删除排序链表中的所有重复元素
（1）这也是一道力扣上面的题目，下面是连接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目样貌：
（2）理解题目
第一、这是一个已经排好序的单链表。
第二、使得这个单链表的每个值只出现一次，需要把重复出现的结点删掉。
（3）使用快慢指针求解
本题，我们依然选择一个快慢指针的思想，也就是前后指针，可以做到时间复杂度为O(n)，也就是只遍历一遍链表就完成
核心思想：我们让快指针先走，如果快指针指向的值和慢指针指向的一样，那就继续往下走，直到指向的值不一样，再修改慢指针的指向，完成重复结点的删除。
第一步：定义快慢指针
ListNode slow = head;
ListNode fast = head.next;第二步：开始遍历链表
while(fast != null) {
while(fast != null && fast.val == slow.val) {
fast = fast.next;
}
if(fast != null) {
slow.next = fast;
slow = fast;
fast = fast.next;
}else {
slow.next = null;
}
}
return head;代码分析：
while(fast != null && fast.val == slow.val) {
fast = fast.next;
}这个while循环是控制快指针，满足条件就继续往下走；出了这个while循环，有两种情况。
第一种：因为fast.val != slow.val而结束，并且没走完链表
if(fast != null) {
slow.next = fast;
slow = fast;
fast = fast.next;
}这种情况就需要连接快慢指针，从而达到删除重复结点的目的
第二种：fast == null，链表走完了
else {
slow.next = null;
}快指针走完了都没满足条件，说明slow后面的结点都是重复的结点
第三步：分析特殊情况
当结点是空的时候，不需要删除；当只有一个结点的时候，也不存在重复结点的情况
if(head == null) {
return null;
}
if(head.next == null) {
return head;
}
在时间效率上面，直接超越百分百
还有一道力扣题和这题的思路很相似，下面是链接，同学们可以先自己尝试
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目要求为：删除所有的key结点
3.快慢指针的小总结
（1）以上是快慢指针的三种常规用法，有的时候，也称为前后指针
（2）当题目中要求只遍历一遍链表，就应该想到快慢指针，一般只需要定义两个变量即可（快慢指针）
（3）当题目的要求有对链表的两头进行操作时，考虑求中间的结点
（4）使用快慢指针，要重点考虑它们的线性关系（分别走多少步）和结束条件文章来源：https://www.toymoban.com/news/detail-765995.html
以上就是本节的全部内容了，同学们快去练手吧！文章来源地址https://www.toymoban.com/news/detail-765995.html
到了这里，关于快慢指针该如何操作？本文带你认识快慢指针常见的三种用法及在链表中的实战的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
