【出自ALBB笔试题】
难度系数:★★★★☆ 被考察系数:★★★★★
题目描述:
单链表有环指的是单链表中某个结点的next域指向的是链表中在它之前的某一个结点,这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在?
分析与解答:
方法一:蛮力法
定义一个HashSet用来存放结点的引用,并将其初始化为空,从链表的头结点开始向后遍历,每遍历到一个结点就判断HashSe中是否有这个结点的引用,如果没有,说明这个结点是第一次访问,还没有形成环,那么将这个结点的引用添加到指针HashSet中去。如果在HashSet中找到了同样的结点,那么说明这个结点已经被访问过了,于是就形成了环。这种方法的时间复杂度为O(N),空间复杂度也为O(N)。
方法二:快慢指针遍历法
定义两个指针fast(快)与slow(慢),二者的初始值都指向链表头,指针slow每次前进一步,指针fast每次前进两步,两个指针同时向前移动,快指针每移动一次都要跟慢指针比较,如果快指针等于慢指针,就证明这个链表是带环的单向链表,否则,证明这个链表是不带环的循环链表。实现代码见后面引申部分。
引申:如果链表存在环,那么如何找出环的入口点
分析与解答:
当链表有环的时候,如果知道环的入口点,那么在需要遍历链表或释放链表所占的空间的时候,方法将会非常简单,下面主要介绍查找链表环入口点的思路。
如果单链表有环,那么按照上述方法二的思路,当走得快的指针fast与走得慢的指针slow相遇时,slow指针肯定没有遍历完链表,而fast指针已经在环内循环了n圈(1<=n)。如果slow指针走了s步,则fast指针走了2s步(fast步数还等于s加上在环上多转的n圈),假设环长为r,则满足如下关系表达式:
2s=s+nr(www.xing528.com)
由此可以得到:s=nr
设整个链表长为L,入口环与相遇点距离为x,起点到环入口点的距离为a。则满足如下关系表达式:
a+x=nr
a+x=(n-1)r+r=(n-1)r+L-a
a=(n-1)r+(L-a-x)
(L-a-x)为相遇点到环入口点的距离,从链表头到环入口点的距离=(n-1)*环长+相遇点到环入口点的长度,于是从链表头与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。实现代码如下:
程序的运行结果如下:
有环
环的入点为:3
运行结果分析:
示例代码中给出的链表为:1->2->3->4->5->6->7->3(3实际代表链表第三个结点)。因此,IsLoop函数返回的结果为两个指针相遇的结点,所以,链表有环,通过函数FindLoopNode可以获取到环的入口点为3。
算法性能分析:
这种方法只需要对链表进行一次遍历,因此,时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息,因此,空间复杂度为O(1)。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。