/ Programming

如何检查单链表是否存在循环

今天在复试的群里看到有个去年的学长被问到如何检查单链表里存在循环。思索一番,并查询了些资料,找到如下方法:

哈希法

具体方法为遍历指针,对每一个指针地址进行哈希,若存在相同的哈希值,则几乎可以确定存在循环。
该方法需要额外的哈希表,空间复杂度为O(n)

反转链表发

该方法的思路是:将链表做一次反转,若最后尾部不能指回head指针,则说明存在循环。
该方法的缺点是在检验之后,需要将链表进行再一次反转,以得到原链表。

快慢指针法

该方法仅限于判断单链表是否是循环链表,若只是有循环结,则不能判定,即快指针追不上慢指针。

设置两个快慢不同的指针(例如慢指针每个函数周期前进1个node,快指针每个函数周期前进2个node),若快指针追上了慢指针,则说明链表为循环链表。

明天就是海大的研究生复试面试了,祝我一切顺利吧!

如何检查单链表是否存在循环
Share this

Subscribe to Zed's Blog