单链表是否有环,两种方式搞定

单链表是否有环,两种方式搞定!

微信搜索公众号“兮一昂吧”,点关注不迷路!

背景

数据结构是我们程序员的基本功,无论是在日常工作还是在求职面试中都会经常用到;而且近年来程序员的工作竞争越来越大,数据结构和算法在大厂的面试中都成了必考题。我所了解的:华为技术人员招聘必须先通过机试才能获得面试机会,机试为两道数据结构编码题,每道题200分总分400,240分可通过。字节跳动面试考察算法是出名了的,不必多说。我所经历的美团面试也都考察了数据结构和算法。

由于我们的日常开发工作往往集中在业务逻辑代码的编写,并且运行在Spring等优秀的框架之上,JDK的数据结构虽然熟练使用,但是对于底层逻辑及数据结构的了解少之又少,所以这就导致了面试中的数据结构与算法题目变成了“送命题”。因此,我们开发人员在日常工作中需要多关注这些常用的数据结构、算法,功夫用在平时,多积累,这样在求职时才能够得心应手。

问题

最近有同事到某几个大厂面试,都问到了链表相关的数据结构问题,比如单链表是否有环及环的入口检测问题、单链表元素去重问题、单链表逆置问题等。我研究练习了“单链表是否有环及环的入口检测问题”,作为日常积累,分享给大家。通过下图,了解一下单链表有环和无环的两种情况。

image.png

作为链表的第一篇,先看下如何构建链表。简单起见,直接上代码(如下)。为了接下来演示方便,我提供了两种链表的构建方式。第一种方式的目标是根据输入的数组从前往后创建单链表;第二种方式的目标是创建带环的链表,带环的依据是输入的数组序列中有且只有一个重复元素。

/**

*链表节点

*/

publicclassNode{

publicNode(int data){

this.data = data;

next=null;

}


publicint data;

publicNodenext;

}


/**

*构建链表(无环)

*/

privatestaticNode buildLinklist(int[] texts){

Node head =newNode(0);

Node node = head;

for(int text : texts){

Nodenext=newNode(text);

node.next=next;

node =next;

}

return head;

}


/**

*构建链表,可能有环

*/

privatestaticNode buildCircleLinklist(int[] texts){

Node head =newNode(0);

Node node = head;

// 存储已经创建过的节点

Map<Integer,Node> nodeMap =newHashMap<>();

for(int text : texts){

Nodenext=null;

if(nodeMap.containsKey(text)){

next= nodeMap.get(text);

}else{

next=newNode(text);

nodeMap.put(text,next);

}


node.next=next;

node =next;

}

return head;

}

解法一:辅助空间法

单链表是否有环及环的入口检测问题,从题目可以知道,这其实是两个问题。一是:检测单链表中是否存在环;二是:如果存在环,则找到环的入口节点。所以,我们必须先解决第一个问题。

从头节点遍历链表,我们会发现:若链表中存在环,我们将无法找到链表的尾节点,一旦遍历过程进入环,遍历过程将在环内转圈,永远停不下来;若链表中不存在环,在有限的步骤内,我们的遍历过程就会停止。所以,从链表遍历的角度来看,我们可发现链表有环和无环的区别:

无环:在有限步骤内,我们可以找到链表的尾节点,即:存在一个节点指向空地址。 有环:永远无法找到尾节点,并且会在环内循环。

试想一下:如果我们的遍历过程是有记忆的,记住所有走过的节点(从内存上来看每个节点都是唯一的),那么我们会得出以下结论:

无环:遍历过程中从头到尾每个节点都是不同的,上图结果为:1-2-3-4-5-6-7-8-9-10-11; 有环:遍历过程中,一旦进入环的循环过程,环内的节点将会重复出现,上图结果为:1-2-3-4-5-6-7-8-9-10-11-4-5-6-7-8-9-10-11-4-5-6……。

所以,我就得出了今天的第一种解法,即: 借助辅助空间,存储遍历过程中所有经过的节点唯一信息,每遍历一个节点检查其是否重复出现过,若遍历过程结束也没有发现重复节点,即可说明链表无环;若遍历过程中出现节点重复时,即可说明链表有环,并且第一个重复的元素为环的入口。

补充说明一点:节点唯一信息是通过Node对象的hashCode识别的,对于Node这个类,我并没有重写hashCode()方法,它代表的是对象的内存地址。

具体实现的代码如下所示:

/**

*检查链表中是否有环:采用node唯一信息,配合HashMap

*

*@param head 头节点

*@return若为空,则不存在环;不为空,则输出为入口节点

*/

privatestaticNode detectCircleByExtraSpace(Node head){

// 用这个map存储所有遍历过的节点

Map<Integer,Node> nodeHashCodeMap =newHashMap<>();

Node node = head.next;

// 节点不空则继续遍历,循环停止的条件有两个:一是遍历到链表尾节点,二是发现重复元素。

while(node !=null){

// 获取节点hashCode

Integer hashCode = node.hashCode();

// 判断是否曾经遍历过

if(nodeHashCodeMap.containsKey(hashCode)){

// 如果曾经遍历过,说明有环,并且这是入口

return node;

}

// 遍历过即加入map

nodeHashCodeMap.put(node.hashCode(), node);

// 下一个

node = node.next;

}

// 走到这里,就说明没有环了。

returnnull;

}

接下来可以写段代码进行测试,下面的例子使用序列“1, 2, 3, 4, 5, 6, 3”创建有环和无环两种链表,结构如下图所示;然后使用detectCircleByExtraSpace进行检测。对于无环的应该输出“无环”,对于有环的应该输出“有环,入口为:3”。

image.png

publicstaticvoid main(String[] args){

int[] texts ={1,2,3,4,5,6,3};

Node head = buildCircleLinklist(texts);

Node node = detectCircleByExtraSpace(head);

printResult(node);


head = buildLinklist(texts);

node = detectCircleByExtraSpace(head);

printResult(node);

}


privatestaticvoid printResult(Node node){

if(node ==null){

System.out.println(“无环”);

}else{

System.out.println(“有环,入口为:”+ node.data);

}

}

上面的例子,输出结果如下,符合预期。

有环,入口为:3

无环

解法二:快慢指针法

熟悉这道题目的朋友,在看到题目时应该就想到了可以使用快慢指针来解决这个问题。一开始我只能理解检测是否存在环这部分,对于入口检测始终搞不明白,经过一阵公司推导,才弄清楚。这个解法的关键在于如何理解问题,以及理解问题后的一些数学公式推导。我试着说明一下快慢指针的解法原理。

首先看链表环的检测。假如把带环的链表比作一条单向的跑道,只能沿着箭头方向跑,那么跑步的人最终将会在环形跑道内转圈。假设,甲乙两人在沿跑道向相同的方向跑步,其中甲的速度是乙的速度的2倍;那么,甲会先进入环形跑道一直绕圈,乙再进入环形跑道。甲乙都进入环形跑道后,就变成了行程问题中的“追及问题”,由于甲的速度大于乙,那么在一段时间后甲肯定会追上乙的。当然,如果链表中没有环,甲的速度大于乙,那么甲会先跑到终点,过程中不会与乙相遇。

所以,我们可以使用上面“追及问题”的方式来解决链表环的检测问题。设置两个指针fast、slow,从链表头部开始向后遍历,fast的速度是slow的两倍。如果fast能够“追上”slow,则说明链表中存在环;若fast遍历完成走到尾节点,则说明链表中不存在环。

然后分析如何找到环的入口。先说结论: 如果链表中存在环,快慢指针相遇后,把fast指针移到链表头部;然后fast和slow以相同的速度(每次移动一个节点)移动,当它们相遇时,相遇的点即为环的入口 。再说如何推导,结合下图进行说明:

image.png

先做几个假设:

假设从头节点到环入口的距离为a,从环入口到fast、slow相遇点的距离为b,从相遇点到环入口的距离为c; 再假设链表的长度为L,环的长度为R; 假设slow走的距离为S,那么fast走过的距离为2S(fast除了走过a+b外,可能还会绕环走n圈)。

那么,就会有以下公式的推导:

image.png

最终得到:

结合上面说的结论(即:fast、slow相遇后,fast从头节点开始移动,slow从相遇点继续移动,fast的速度与slow一致),仔细看下这个公式代表了什么?

a代表了从头节点到环入口的距离,相当于fast走过的距离; c+(n-1)*R代表从slow从相遇点走到环入口后又沿着环走了n-1圈; 以上两者相等即说明:fast、slow会在环的入口相遇;

所以:如果链表中存在环,快慢指针相遇后,把fast指针移到链表头部;然后fast和slow以相同的速度(每次移动一个节点)移动,当它们相遇时,相遇的点即为环的入口。

以上就是快慢指针解法的原理过程,这么看下来其实也是比较容易理解的。但是,如果没有遇到过、听说过,我是真的很难想到这个解法,尤其是第二步查找环入口。好了,理论部分分析完了,我们看下代码该如何实现:

/**

*检测链表是否有环,若有环则找到入口

*使用快慢指针的方式

*

*@param head 链表头节点

*@return若为空,则不存在环;不为空,则输出为入口节点

*/

privatestaticNode detectCircleByFastSlow(Node head){

// 快慢指针从头节点开始

Node fast = head;

Node slow = head;

// 用于记录相遇点

Node encounter =null;

// fast一次走两步,所以要保证next和next.next都不为空,为空就说明无环

while(fast.next!=null&& fast.next.next!=null){

// fast走两步,slow走一步

fast = fast.next.next;

slow = slow.next;

// fast和slow一样,说明相遇了,或者fast追上slow了。

if(fast == slow){

// 记录相遇点,fast或slow都一样

encounter = fast;

// 相遇了,就退出环检测过程

break;

}

}


// 如果encounter为空,说明没有环,就不用继续找环入口了。

if(encounter ==null){

return encounter;

}


// fast回到head位置

fast = head;

// 只要两者不相遇,就一直走下去

while(fast != slow){

// fast每次走一步,slow每次走一步,速度一样

fast = fast.next;

slow = slow.next;

}


// 相遇点,即为环入口

return fast;

}

修改上面的测试代码,会发现与解法一的结果一致。

publicstaticvoid main(String[] args){

int[] texts ={1,2,3,4,5,6,3};

Node head = buildCircleLinklist(texts);

Node node = detectCircleByFastSlow(head);

printResult(node);


head = buildLinklist(texts);

node = detectCircleByFastSlow(head);

printResult(node);

}

总结

本文采用“辅助空间法”和“快慢指针法”两种方式解决了判断单链表是否有环及环入口查找的经典问题,两种方法各有利弊,简单总结如下:

辅助空间法:时间复杂度为O(n),空间复杂度为O(n)。好处是容易想到,容易理解;坏处是会消耗额外的辅助空间; 快慢指针法:时间复杂度为O(n),空间复杂度为O(1)。性能较好,但是不容易理解。

数据结构与算法的重要性文章开头已经说了,我还想再补充一些:虽然看起来很难,但是这些常见的问题、解法都是固定的,只要我们多积累、多练习、多思考,并且灵活运用到工作中去,就会发现它其实没有想象中那么难。

如果本文对你有帮助,麻烦转发给更多的朋友看到!

公众账号
我还没有学会写个人说明!
上一篇

CSS 实现各种 Loading 效果附带解析

你也可能喜欢

评论已经被关闭。

插入图片