从判断一个
单链表是否存在循环而扩展衍生的问题,有则称之为有环链表问题。
链表在面试中出现的频率很高,有的比较正常,考链表的常规操作,主要看基本功是否扎实,有些就比较难,难在思维的改变和是否能够想到对应的点。这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个
单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。
第一种方法,将所有的遍历过的节点用某个结构存储起来,然后每遍历一个节点,都在这个结构中查找是否遍历过,如果找到有重复,则说明该链表存在循环;如果直到遍历结束,则说明链表不存在循环。
这个结构我们可以使用hash来做,hash中存储的值为节点的内存地址,这样查找的操作所需时间为O(1),遍历操作需要O(n),hash表的
存储空间需要额外的O(n)。所以整个算法的
时间复杂度为O(n),
空间复杂度为O(n)。
当有环的时候,最后
指针会定位到链表的头部,如果到最后,都没有再到头部,那说明链表不存在循环。
第三种方法,可能大家已经知道了,同时也是面试官大多想要得到的答案,就是快慢
指针。
快
指针pf(f就是fast的缩写)每次移动2个节点,慢指针ps(s为slow的缩写)每次移动1个节点,如果快指针能够追上慢指针,那就说明其中有一个环,否则不存在环。
其实第三种解法存在问题,当一个存在环的链表足够长,而环足够小,那么会存在快指针永远不会追上慢指针的情况。快慢指针只适用于环出现在链表尾部的情况,也就是单链表环的问题,而无法解决链表存在循环的问题。