详细总结快慢指针的在链表中的常见题型

悠悠 2023-09-23 17:39 46阅读 0赞

### 常见快慢指针题型 ###

*  1.找出链表中间结点
 *  2.找到倒数第K个结点
 *  3.判断环形链表
 *  4.找到环形链表的入口（进阶）
 *  5.相交链表

# 1.找出链表中间结点 #

![在这里插入图片描述][65a9cbf6e83b4ee1bc125dc18f58294a.png]

**双指针进阶解法**

> 1.定义两个指针，一个快指针，一个慢指针。  
> 2.快指着一次走两步，慢指针一次走一步  
> 3.考虑快指针指向哪里时，我们的慢指针刚好走到中间结点

用两个指针 `slow` 与 `fast` 一起遍历链表。`slow` 一次走一步，`fast` 一次走两步。那么当 `fast` 到达链表的末尾时，`slow` 必然位于中间。

> 1.定义快慢指针  
> 2.快指针一次走一步，慢指针一次走两步  
> 3.当快指针为`null`或快指针的`next为null`时退出循环

![在这里插入图片描述][a339911e2e934806968f754552d4b298.gif_pic_center]

> 前提讲到了，如果有两个中间结点，则返回第二个中间结点，所以我们再看一下这个解法对于结点个数为偶数个的还是否合适

![在这里插入图片描述][4e853f72924a43b7956097613d20e21f.gif_pic_center]  
看图可以知道，无论该链表是奇数个还是偶数个，都不会影响最终的结果。

> 判断条件：  
> 当`fast==null`时，或者`fast.next==null`时，退出循环。  
> **注意**：由于逻辑运算符&&是先判断左侧，左侧为真再去判断右侧，如果我的`fast`已经是`null`，那么如果我将`fast.next`写在左侧就会产生空指针异常，所以我们需要先判断fast是否为`null`，也就是将`fast!=null`写在左侧

**代码如下**

class Solution {
        
        public ListNode middleNode(ListNode head) {
        
        //定义两个指针，一个快指针，一个慢指针
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;//慢指针一次走一步
                fast = fast.next.next;//快指针一次走两步
            }
            return slow;//返回慢指针
        }
    }

**复杂度分析：**

*  时间复杂度**O(n)**,其中 `N` 是给定链表中的结点数目。
 *  空间复杂度**O(1)**,只需要常数空间存放 slow 和 fast 两个指针。

# 2.找到倒数第K个结点 #

![在这里插入图片描述][e8b95b9b31c94675872c30928dfe0586.png]

解题思路：

> 定义一个快慢指针，先让快指针走K步，然后慢指针和快指针一起走，当快指针为null时，我们的慢指针就是倒数第K个数。

究竟上面的原理是如何推理出来的呢？

我们看图演示

![在这里插入图片描述][fd2bc2cd3ab8443eb563476790ed9569.png]

> 第一步：先让快指针cur走K步，如图二  
> 第二步：快指针，慢指针一起走，当快指针为null时退出循环  
> 第三步：此时prev就是倒数第K个结点，返回prev就行

具体过程如下

![在这里插入图片描述][0e5ae207ba8f40589befd94f5280c8b3.gif_pic_center]

> 使用如图的快慢指针，首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点

**代码入下**  
注意注释！！！

public class Solution {
        
        public ListNode FindKthToTail(ListNode head,int k) {
        
    		 //判断链表是不是为空，并且k不能小于等于0	
            if (k<=0||head==null) {
        
                return null;
            }
            int n=0;
            ListNode prev=head;
            ListNode cur=head;
            while (n<k) {
        
            //判断cur是否为null
            //如果为null返回null
                if (cur==null) {
        
                   return null;
                }
                cur=cur.next;
                n++;
                //如果将if放到下面，
                //那么判断倒数第n个结点时就会出错，n是链表长度，
                //也就是查找链表头节点时会报错
                //if (cur==null) {
        
                // return null;
                // }
            }
            while (cur!=null) {
        
                prev=prev.next;
                cur=cur.next;
            }
            return prev;
        }
     }

作者总结：

有一个极端条件就是当倒数第K个结点是头节点时，不能将if放到我在代码注释的那个位置，如下图  
![在这里插入图片描述][057a8e00acf34ab38fbc863570154ad4.png]

> 如果在下面判断当`cur == null`时就退出，那么存在一种情况就是当我的`cur==null`时，我的prev就是倒数第5个结点符合条件，如果此时退出结果就会和预期结果不一样，所以我们将判断的条件写在了上面，那样的话，只有当我们的n没有符合条件时并且`cur==null`，才返回null,这样就避免了上面的错误

输入一个链表，输出该链表中倒数第k个结点[oj题][oj]

# 3.判断环形链表 #

![在这里插入图片描述][d0b52bc8b2944842b1c4a78de9e03cae.png]

题目描述：

> 给你一个链表，判断是否带环，如果带环返回`true`否则返回`false`

**快慢指针解法**：

> 假设同学「A」和同学「B」相约一起跑步，他们一起从宿舍楼出来，由于「A」跑得快，所以「A」率先到达操场进行跑圈，如果不是跑圈（没有环），那么「B」永远都不会追上「A」,等到「B」同学进入操场时，由于「A」的速度快，它一定会在某个时刻与「B」相遇，即比「B」多跑了若干圈.

我们可以借助上面的思路来解决本题：

> 1.设置一个快慢指针  
> 2.快指针一次走二步，慢指针一次走一步  
> 3.当快指针为空或者快指针的下一个结点为空退出循环（这样就说明不带环）返回`false`  
> 4.当慢指针追上快指针时，说明带环，返回`true`

我们看下图：

![在这里插入图片描述][b1b3cc30824a42dfb45cf7b3672abf9c.gif_pic_center]  
**代码如下**：

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            ListNode A=head;//快指针
            ListNode B=head;//慢指针
            while(A!=null&&A.next!=null) {
        
                A=A.next.next;//快指针一次走两步
                B=B.next;//慢指针一次走一步
                //当两个结点相同时，意思就是相遇了
                if(A==B) {
        
                    return true;//返回正确
                }
            }
            return false;//当出了循环说明这个链表没有环，返回错误
        }
    }

复杂度分析  
时间复杂度：O(N)O(N)O(N)，其中 NNN 是链表中的节点数。

空间复杂度：O(1)O(1)O(1)。我们只使用了两个指针的额外空间  
**复杂度分析：**

*  时间复杂度O(n),其中 `N` 是给定链表中的结点数目。

> 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。  
> 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，又因为慢指针最多走N次，因此至多移动 N 轮。（下面讲解）

*  空间复杂度O(1),只使用了两个指针额外空间

**为什么慢指针至多移动N次**？（N是链表长度）

> 我们可以想象，两个人在跑步，由于「A」同学跑的快，所以在一定会遇到「B」同学，前提不是讲到了嘛，「A」同学的速度是「B」同学的二倍，所以当「B」同学跑完一圈时，「A」同学一定跑完了两圈（A的起点为B同学进入操场时，A同学的当前位置来算)，所以无论怎样，他们都一定会相遇，

**为什么快指针一定是一次两步，如果一次三步，一次四步可不可以**？

**举例**：

> 答案是不可以的！可能在数学中你们是能算出相遇的时间或者相遇时移动的次数（那是因为数学中有小数的存在），但是链表不一样，它的每一步都是整数，不存在小数这一说，就像小时候玩的飞行棋，假如在距离你一个格子的位置有一个宝箱，那么你走四步，三步，甚至是两步你都不会吃到这个宝箱，只能眼睁睁的看着和它擦肩而过，就和你处心积虑想要跟你的女神制造一个偶遇的机会一样，她三点出门，你呢？三点零一分走到她的宿舍楼底下，那么你们就不会相遇，这就是错过，一分一毫都不能差。所以我们在追赶爱情的过程中，把握住时宜，宁可早来，不可迟到，可能你不知道她什么时候回来，但是你要做好准备，哪怕早来六个小时，哪怕是雪天，哪怕是你站在街上为了耍酷只穿一个薄薄的外套而被冻成冰棍，你也不要放弃，这些付出，在你最后和她在一起时，都是值得的！（故事来B站某位宋老师，咳咳有点跑题）

**回归正题**

如果一次走三步：

> 有一种极限情况，假如你这个环是奇数，那么你和他的距离（3-1=2）每次缩短两步，一个奇数无论减去多少个偶数，依然是个奇数，你们不会相遇，有的只是无穷的错过

如果一次四步：

> 如果这个环是偶数，那么你和它的距离是以每次（4-1=3）三个距离的位置缩短，如果这个环是偶数，它每次距离减 3，（在极端条件下）无论减多少次他都不会相遇。

如果每次走两步：

> 不管奇数偶数，由于我每次走两步，我们直接的距离每次缩短（2-1=1）1步，所有的整数都是1的倍数，我们终会相遇！

# 4.找到环形链表的入口（进阶） #

![在这里插入图片描述][c736680282ab4b8daebb2d55716dabed.png]

> 题目：判断是否是循环链表，如果该链表带环则返回进入环的第一个结点.

**快慢指针解法**：

这个其实就涉及到数学的知识了，我们依旧是画图举例。

![在这里插入图片描述][bd3bc959ddd44b608d0a2228d19e514c.png]

我们此时就可以认为`L`是没进入环时的长度，`X`的长度是从进入环的第一个结点开始计算直到快慢指针相交时的距离。`C`是环内剩下的长度。

> 慢指针一次走一步，快指针一次走两步

所以我们可以推导出

> 慢指针走的的长度：L+x  
> 快指针走的长度：L+x+k(x+c)  
> x+c=环的周长

因为可能会存在，**环**很短，`L`很长的这种情况，如果是这种情况，那么快指针就需要重复走好多遍这个**环**，所以就是`k(x+c)`。

通过上面的公式可以算出：

由于快指针的速度是慢指针的二倍，所以当**慢指针** **×** 2才是**快指针**走的距离

> 2（L+x）=L+k(x+c)+x  
> //下面是去括号，移项，合并同类型  
> L+x=x+c+(k-1)(x+c)  
> L=c+(k-1)(x+c)  
> L-(k-1)(x+c)=c

我们假设两个结点A,B如图

![在这里插入图片描述][3fb6431e5ec74d1c90fb90ecdc8ad65c.png]

> 不管我的A指针走了多少个（x+c）我的A指针的位置依旧没变，但是我的B指针却往前移动了(k-1)(x+c)个位置，所以，当走完了(k-1)(x+c)时，我们的B距离环形入口只剩下c个结点，又因为我们的A指针距离环的入口也是c个结点，所以他们相交的位置就是环的入口。

我们不能判断这些变量究竟为几，但是我们通过查找他们直接的关系，就可以找到正确答案！

**图片如下：**

**第一步：找到交点**

![在这里插入图片描述][3f44882e5112496e8c638685d6bec101.gif]

**第二步：两个指针一个从头变量，一个从相交结点开始**

![在这里插入图片描述][7273a83b2ef7450d945f9fe49157903a.gif]

**代码如下：**

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            
            ListNode A=head;//慢指针
            ListNode B=head;//快指针
            //找到交点
            while(B!=null&&B.next!=null) {
        
    				//①
                B=B.next.next;
                A=A.next;
                //切记不可以写在①那个位置
                if(A==B) {
        
                    break;
                }
            }
            //判断因为什么退出循环
            //如果是因为结点为空，则直接返回null
            if(B==null||B.next==null) {
        
                return null;
            }
            //
            B=head;//B指针是头节点的位置
            //相交时，他们的交点就是环的入口结点
            while(A!=B) {
        
                A=A.next;
                B=B.next;
            }
            //返回A,B都行
            return A;
        }
    }

**注意：**

> 注释中提到了，`if()`不可以写在①的那个位置，因为他们开始时本身就是相同的，如果写在了一起，那么就会发生直接退出循环！！！

**复杂度分析：**

*  **时间复杂度**：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，`prev`指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)
 *  **空间复杂度**：O(1)。我们只使用了 `A B` 2个指针。

# 5.相交链表 #

![在这里插入图片描述][9d9c640c6e11480a87f15bb34b1fc676.png]

**题目**：

> 给你两个链表，判断是否相交，若相交，返回相交结点！

**解法一：暴力解法**

> 上面链表的每一个结点都和下面的整个链表进行对比，最坏情况下，如果两个链表不相交，时间复杂度是O(n^2),所以这里就不演示了，我们讲解时间复杂度为O(n)的解法

**解法二：双指针遍历**

**思路：**

> 我们可以定义两个指针，分别从两个链表的头开始遍历，然后找到求出链表的差值，长的链表走完差值，两个链表一起向后遍历，相同时退出，返回相同的结点。

**具体步骤：**

> 1.定义两个指针，分别从两个链表的头开始向后遍历  
> 2.记录两个链表的长度  
> 3.求出链表长度的差值  
> 4.长的链表先走完差值  
> 5.两个链表再同时向后遍历，直到相同时退出

如图：

**第一步：遍历相交链表**

![在这里插入图片描述][d2262a0d38f64e9f8f3295b42c6946af.gif_pic_center]  
**第二步：长链表先走完差值,再一起走**

![在这里插入图片描述][767dce6fd1804ef6a8fde925b45c0990.gif_pic_center]

**代码如下**：

public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
    		// 一个链表为空永远不可能香蕉
            if (headA==null&&headB==null) {
        
                return null;
            }
            //分别记录headA headB
            ListNode A= headA;
            ListNode B=headB;
            //用来记录链表长度
            int count=0;
            //用来记录最短长度
            int sum=0;
            //用来判断哪个链表长
            boolean p=false;
            //两个链表一起走，有一个为空时，最短长度记录完成
            while (A!=null&&B!=null) {
        
                A=A.next;
                B=B.next;
                count++;
                sum++;
            }
            //继续走长的链表，直到长链表也走完，记录长链表的长度
            
            while (A!=null) {
        
                A=A.next;
                count++;
                //如果是A链表不为空，那么p为true
                p=true;
            }
            //同上
            while (B!=null) {
        
                B=B.next;
                //如果是B链表不为空则p不变
                count++;
            }
            //重新找到头
            A=headA;
            //同上
            B=headB;
            //让长的先走
            int n=count-sum;
            //P为真A先走n步
            if (p) {
        
                while (n>0) {
        
                    A=A.next;
                    n--;
                }//否则B先走
            } else {
        
                while (n>0) {
        
                    B=B.next;
                    n--;
                }
            }//走完链表的差值后，两个链表一起遍历
            //香蕉退出循环
            while (A!=B) {
        
                A=A.next;
                B=B.next;
            }
            return A;
        }
    }

**复杂度分析：**

*  **时间复杂度**：O(N)，总共遍历了一次完成的长链表外加找交点时遍历了一次链表，总共遍历了2\*n次（n代表最长链表的长度）
 *  **空间复杂度**：O(1)，

[65a9cbf6e83b4ee1bc125dc18f58294a.png]: https://img-blog.csdnimg.cn/65a9cbf6e83b4ee1bc125dc18f58294a.png
[a339911e2e934806968f754552d4b298.gif_pic_center]: https://img-blog.csdnimg.cn/a339911e2e934806968f754552d4b298.gif#pic_center
[4e853f72924a43b7956097613d20e21f.gif_pic_center]: https://img-blog.csdnimg.cn/4e853f72924a43b7956097613d20e21f.gif#pic_center
[e8b95b9b31c94675872c30928dfe0586.png]: https://img-blog.csdnimg.cn/e8b95b9b31c94675872c30928dfe0586.png
[fd2bc2cd3ab8443eb563476790ed9569.png]: https://img-blog.csdnimg.cn/fd2bc2cd3ab8443eb563476790ed9569.png
[0e5ae207ba8f40589befd94f5280c8b3.gif_pic_center]: https://img-blog.csdnimg.cn/0e5ae207ba8f40589befd94f5280c8b3.gif#pic_center
[057a8e00acf34ab38fbc863570154ad4.png]: https://img-blog.csdnimg.cn/057a8e00acf34ab38fbc863570154ad4.png
[oj]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[d0b52bc8b2944842b1c4a78de9e03cae.png]: https://img-blog.csdnimg.cn/d0b52bc8b2944842b1c4a78de9e03cae.png
[b1b3cc30824a42dfb45cf7b3672abf9c.gif_pic_center]: https://img-blog.csdnimg.cn/b1b3cc30824a42dfb45cf7b3672abf9c.gif#pic_center
[c736680282ab4b8daebb2d55716dabed.png]: https://img-blog.csdnimg.cn/c736680282ab4b8daebb2d55716dabed.png
[bd3bc959ddd44b608d0a2228d19e514c.png]: https://img-blog.csdnimg.cn/bd3bc959ddd44b608d0a2228d19e514c.png
[3fb6431e5ec74d1c90fb90ecdc8ad65c.png]: https://img-blog.csdnimg.cn/3fb6431e5ec74d1c90fb90ecdc8ad65c.png
[3f44882e5112496e8c638685d6bec101.gif]: https://img-blog.csdnimg.cn/3f44882e5112496e8c638685d6bec101.gif
[7273a83b2ef7450d945f9fe49157903a.gif]: https://img-blog.csdnimg.cn/7273a83b2ef7450d945f9fe49157903a.gif
[9d9c640c6e11480a87f15bb34b1fc676.png]: https://img-blog.csdnimg.cn/9d9c640c6e11480a87f15bb34b1fc676.png
[d2262a0d38f64e9f8f3295b42c6946af.gif_pic_center]: https://img-blog.csdnimg.cn/d2262a0d38f64e9f8f3295b42c6946af.gif#pic_center
[767dce6fd1804ef6a8fde925b45c0990.gif_pic_center]: https://img-blog.csdnimg.cn/767dce6fd1804ef6a8fde925b45c0990.gif#pic_center