软件开发的家园,编程爱好者的天地.

现在是:北京时间 2016/4/14 上午11:50:51 星期四

设为首页  |  加入收藏  |  网站地图

链表面试题之有环链表问题
发布于:第八基地 来源:互联网 作者:天堂路上 时间:2016-04-25 点击:207

链表在面试中出现的频率很高,有的比较正常,考链表的常规操作,主要看基本功是否扎实,有些就比较难,难在思维的改变和是否能够想到对应的点。这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。

首先来看最基本的这个问题:如何判断一个单链表是否存在循环,链表数目未知。算法不能破坏链表。

这里我们可以想到有三种解决的方法。

第一种方法,将所有的遍历过的节点用某个结构存储起来,然后每遍历一个节点,都在这个结构中查找是否遍历过,如果找到有重复,则说明该链表存在循环;如果直到遍历结束,则说明链表不存在循环。

这个结构我们可以使用hash来做,hash中存储的值为节点的内存地址,这样查找的操作所需时间为O(1),遍历操作需要O(n),hash表的存储空间需要额外的O(n)。所以整个算法的时间复杂度为O(n),空间复杂度为O(n)。

第二种方法,比较的特别,是使用反转指针的方法,每过一个节点就把该节点的指针反向。

当有环的时候,最后指针会定位到链表的头部,如果到最后,都没有再到头部,那说明链表不存在循环。

这个方法会破坏掉链表,所以如果要求是不能破坏链表的话,我们最后就还需要反转一下,再将链表恢复。

这个方法使用的空间复杂度为O(1),其实是使用了3个指针,用于进行反转。同时,时间复杂度为O(n)。

第三种方法,可能大家已经知道了,同时也是面试官大多想要得到的答案,就是快慢指针。

快指针pf(f就是fast的缩写)每次移动2个节点,慢指针ps(s为slow的缩写)每次移动1个节点,如果快指针能够追上慢指针,那就说明其中有一个环,否则不存在环。

这个方法的时间复杂度为O(n),空间复杂度为O(1),实际使用两个指针。

【扩展】 

对于这个问题,还有一些扩展性的问题。比如:如何找到环的开始节点也就是环首,如何得到环的长度,如何解开环等等,其中的关键就是如何找到其中对应的规律。 

当快慢指针都进入环之后,可以观察到快指针每次都接近慢指针一个节点位置。这样,当两个指针相遇的时候,其从慢指针进入环开始走过的路程肯定是小于环的长度x的。而假设链表的第一个节点到环的开始节点的长度为y。

画图可以得知:

 

 

 

 

 

 

 

 

 

 

 

 

 

根据图上面的示意,快指针pf需要追z个节点,就可以追上慢指针ps,而一个iteration中pf会追上ps一个节点,所以需要用z个iteration。

当ps和pf相遇了,可以肯定的是这两个指针肯定是在环上相遇的。

此时,还是继续一快一慢,根据上面得到的规律,经过环长x,这两个指针第二次相遇。这样,我们可以得到环中一共有多少个节点。

 

 

 

 

 

 

 

 

 

 

 

 

 

假设相遇点为Q点,Q点到m点的距离为r,第一次相遇的时候,ps走的距离为y+z,而pf走的距离为2y+2z,要求环的开始节点位置,也就是求得y的值即可。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

当重合的时候,pf走了2*all步,ps走了all步,此时两个指针都以步长为1进行回退,那ps就回退到第一个节点W,而pf回退到ps的位置。ps的位置就是Q点,此时从W点或Q点出发,x步之后,都会落到黄色的点Q点上。那因为此时使用的两个指针都是步长为1的,那第一个重合的点是哪个呢?

可以看出是环首的红色点m。而使用的步长就是y。

 

所以总结如下:

使用快慢指针,第一次相遇,表明存在循环。

继续快慢指针,第二次相遇,得到的iteration步长为环的长度。

分别从相遇点和第一个节点出发,都是步长为1的指针,当相遇时,得到的iteration步长为环首的位置。

这个题目的特殊情况就是指针指向的就是第一个节点,那得到的就是一个循环链表。

附上扩展题的代码

Code
 1 bool hasLoop(linkedlist llist)
 2 {
 3     listnode *pf=llist;
 4     listnode *ps=llist;
 5 
 6     while(true)
 7     {
 8         if(pf && pf->next)
 9         {
10             pf=pf->next->next;
11         }
12         else
13             return false;
14 
15         ps=ps->next;
对我有帮助
(0)
0%
对我没帮助
(0)
0%
返回顶部
在线反馈
在线反馈