环形链表进阶版【手绘漫画】面试必考之双指针(LeetCode 142)

在这里插入图片描述

图解算法与数据结构

1、前言

今天开始的是双指针!

下面一起来看看吧!!!
在这里插入图片描述
让我们从一个经典问题开始:

给定一个链表,判断链表中是否有环。

你可能已经使用 哈希表 提出了解决方案。但是,使用 双指针 技巧有一个更有效的解决方案。

想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况:

  1. 如果没有环,快指针将停在链表的末尾。
  2. 如果有环,快指针最终将与慢指针相遇。

所以剩下的问题是:

这两个指针的适当速度应该是多少?

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

为了让你更懂,下面来看一个题吧!
在这里插入图片描述

2、实例

LeetCode 142,一个求证链表中有没有环的题。
在这里插入图片描述
在这里插入图片描述

3、正文

一起来看一下:

  1. 双指针初始化:

    1. 设双指针 fastslow 指向链表头部 head
    2. fast 每轮走 1 步;
    3. slow 每轮走 1 步;
  2. 两种情况

    1. 第一种情况:不出意外,fast 每轮再多走 1 步(这才是名副其实的快指针~);
      在这里插入图片描述
    2. 第二种情况fast 走到链表末端,下一节点为空,说明链表无环,直接 break,返回 NULL(如果存在环,两个指针必然会相遇,追击问题,fast 速度是 slow 的二倍~);
      在这里插入图片描述
  3. 双指针第一次相遇(当 fast == slow 时)

    1. 设链表共有 a+b 个节点,其中 链表头到环的入口a 个节点(不算环入口节点),b 个节点,若两指针分别走了 fs 步(fast,slow 的英文缩写);
    2. 路程等于速度乘以时间,fast 的速度是 slow 的 2 倍,所以 fast 走的步数是 slow 的 2 倍,即 f = 2*s ①;
    3. 双指针最后都是在环内绕圈直到重合,所以 fastslow 多走了 n 个环的长度,即 f = s + n*b ②;
    4. 以上两式 ① ② 相减得:f = 2n*bs = n*b,即 fastslow 分别走了 2nn
      在这里插入图片描述
  4. 双指针第二次相遇(当 fast == slow 时)

    1. slow 指针不动,fast 重新指向链表头节点(f = 0,s = n*b);
    2. slowfast 同时每轮向前走 1 步;
    3. fastf = a 步时,slows = a+nb 步,此时 两指针重合,并同时指向环入口b 是环的长度!整数倍 b 就是环入口)。
      在这里插入图片描述
  5. 返回 fast 指针指向的节点(slow 也行,因为终止条件是 fast == slow)。


这个位置有个非常灵性的操作,即:
在这里插入图片描述
分析分析

:如何才能恰好在环入口节点相遇呢?

:如果走过的路程满足 a+n*bn 可以是任意自然数值(0,1,2…),先走 a 步到环入口节点,之后无论绕多少圈环(n*b 步)都会再次回到入口节点,即相遇了~~~~而现在这个时间点,slow 走过的步数是 nb,只要想办法再走 a 步停下来,就可以到环的入口,同时 fast 也要走 a 步,这样两者就相遇了!所以依然是双指针法,fast 重新初始化为链表头 head,这样走 a 步就到了环入口,而 slow 也走 a 步,变成了 a+n*b,到达了环入口节点。

妙啊!!!
在这里插入图片描述
在这里插入图片描述

4、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto fast=head,slow=head;
        while(fast){
            fast=fast->next;
            slow=slow->next;
            if(fast) fast=fast->next;
            else break;

            if(fast==slow){
                fast=head;
                while(fast!=slow){
                    fast=fast->next;
                    slow=slow->next;
                }
                return fast;
            } 
        }
        return NULL;
    }
};

在这里插入图片描述
在这里插入图片描述

如果有幸帮到你,请帮我点个【赞】,给个【关注】!如果能顺带【评论】给个鼓励,我将不胜感激。

如果想要更多的资源,欢迎关注 @我是管小亮,文字强迫症MAX~

互联网寒冬背景下!数据分析师还吃香吗?缺人吗?
10-31
随着互联网的发展,带火了数据分析、数据挖掘、算法等职业,作为其中门槛相对较低的数据分析一职,成为转行的一个不错选择。
HarmonyOS.rar 华为鸿蒙操作系统 源码 国产操作系统源码 华为源码
08-16
`HarmonyOS` is the first full-scene distributed OS based on micro-kernel. It is an operating system
穿越沙漠问题
07-04
《算法设计与分析》迭代法解决穿越沙漠问题,C++描述。
再也不怕女朋友问我二分查找了!!!【手绘漫画面试必考之二分查找(解题模板和深度剖析),最终回
文章目录1、前言2、万恶之源3、二分查找(LeetCode 704)4、x 的平方根(LeetCode 69)5、猜数字大小(LeetCode 374)6、搜索旋转排序数组(LeetCode 33)7、讨论 1、前言 今天是二分查找的最后一更,来做一下LeetCode中的探索的题~ 【手绘漫画面试必考之二分查找(解题模板和深度剖析),上回 【手绘漫画面试必考之二分查找(解题模板和深度剖析)...
环形链表手绘漫画面试必考之双指针LeetCode 141)
文章目录图解算法与数据结构1、前言2、实例3、正文4、代码 图解算法与数据结构 1、前言 今天开始的是双指针! 下面一起来看看吧!!! 让我们从一个经典问题开始: 环形链表进阶手绘漫画面试必考之双指针LeetCode 142) 上次讲了进阶的,你会发现普通本太easy了~ 还是来看题吧! 2、实例 LeetCode 142,一个求证链表中有没有环的题。 3、正文 一起来看一下...
手绘漫画】图解LeetCode之第一个错误的本(LeetCode 278题)
文章目录图解LeetCode刷题计划1、写在前面2、题目3、正文4、代码 图解LeetCode刷题计划 1、写在前面 手绘漫画系列正式上线!!!“图解LeetCode刷题计划” 来了!!! 今天是第九期,争取每天一期,最多两天一期,欢迎大家监督我。。。 最近依旧是二分查找算法呢~ 使用新的模板加上图解,相信你能更加理解二分法的使用!!! 2、题目 首先看一下题目, 分界条件就是出现错误!...
手绘漫画】图解LeetCode之x 的平方根(LeetCode 69题)
文章目录图解LeetCode刷题计划1、写在前面2、题目3、正文4、代码 图解LeetCode刷题计划 1、写在前面 手绘漫画系列正式上线!!!“图解LeetCode刷题计划” 来了!!! 今天是第七期,争取每天一期,最多两天一期,欢迎大家监督我。。。 最近依旧是二分查找算法呢~ 使用新的模板加上图解,相信你能更加理解二分法的使用!!! 2、题目 首先看一下题目, 分界条件就是我们的 m...
??2020 CSDN 皮肤主题: 酷酷鲨 设计师:CSDN官方博客 返回首页