本文主要是介绍让我们一起来领悟带环问题的核心思想,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、带环的链表:
本质还是快慢指针来解决
关于如下一个带环链表怎么去找到他们想碰到的节点呢????我们可以想到快慢指针,第一个快点走,若是有环就会进入环,此时快指针每次走2步,慢指针走一步,迟早会遇见,速度是2倍关系,两个指针就会相遇(追击问题)!!没环的话快指针走到NULL就出来了!!
二、N个节点是否适用快慢指针的追击:
问题:会不会出现无法相遇的问题,让我们探讨一下,当创造了环的情况下,你的爱情是否能成功!!!!(能否相遇啊)
例1:slow 1 dest 2
先从快指针走2,慢指针走1步进行讲解 看下图,慢指针为 slow 快指针为 dest ,假设快指针走2步 慢指针走1步。这样我们可以列出一个数学表达式,下面的L为初位置到进入环点位置的距离,c为环的长度,还可以设置一个变量 N 表示慢指针进入环时的距离差
如下图:当slow进入环点,各个指针走过的路程;
迟早会相遇的:
例2: 如果快指针走3步呢》》》》》》》》
考虑一下是否会出现N为奇数,C为偶数的情况,接下来我们用数学表达式来进行破解
由上图可知,不会出现无法相遇的情况,依次类推若是为n的话,速度就是n倍关系,然后考虑的N和C,对dest走n步也是如此进行分析,得出结果是一样的
三、总结:
在环链表里面,两个人无论怎样都会相遇,爱情就是兜兜转转还是你,只能是你,该遇见的人迟早会相遇,遇不见的人一辈子也 不会相遇了(非环状的链表,快指针到了NULL就结束了,她也就真的再也追不上了)
这篇关于让我们一起来领悟带环问题的核心思想的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!