Chinaunix首页 | 论坛 | 博客
  • 博客访问: 234271
  • 博文数量: 26
  • 博客积分: 836
  • 博客等级: 军士长
  • 技术积分: 296
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-14 22:52
文章分类

全部博文(26)

文章存档

2013年(2)

2012年(6)

2011年(12)

2009年(6)

我的朋友

分类: C/C++

2012-08-11 14:45:22

转载于:http://blog.csdn.net/vividonly/article/details/6673758

收集了一下链表常见的面试题:

1、如何判断一个单链表有环

2、如何判断一个环的入口点在哪里

3、如何知道环的长度

4、如何知道两个单链表(无环)是否相交

5、如果两个单链表(无环)相交,如何知道它们相交的第一个节点是什么

6、如何知道两个单链表(有环)是否相交

7、如果两个单链表(有环)相交,如何知道它们相交的第一个节点是什么


1、采用快慢步长法。令两个指针p和q分别指向头结点,p每次前进一步,q每次前进两步,如果p和q能重合,则有环。可以这么理解,这种做法相当于p静止不动,q每次前进一步,所有肯定有追上p的时候。

我们注意到,指针pq分别以速度为12前进。如果以其它速度前进是否可以呢?

假设pq分别以速度为v1v2前进。如果有环,设指针pq第一次进入环时,他们相对于环中第一个节点的偏移地址分别为ab(可以把偏移地址理解为节点个数)

这样,可以看出,链表有环的充要条件就是某一次循环时,指针pq的值相等,就是它们相对环中首节点的偏移量相等。我们设环中的结点个数为n,程序循环了m次。

由此可以有下面等式成立:(mod(n)即对n取余)

(a+m*v1)mod(n) = (b+m*v2) mod(n)

设等式左边mod(n)的最大整数为k1,等式右边mod(n)的最大整数为k2,则

(a+m*v1)-k1*n = (b+m*v2)-k2*n

整理以上等式:

m= |((k2-k1)*n+a-b)/( v2-v1)|       

如果是等式①成立,就要使循环次数m为一整数。显然如果v2-v11,则等式成立。

这样pq分别以速度为v1v2|v2-v1|1时,按以上算法就可找出链表中是否有环。当然|v2-v1|不为1时,也可能可以得出符合条件的m。

  1. bool I***itsLoop(slist *head)  
  2. {  
  3.     slist *slow = head, *fast = head;  
  4.   
  5.     while ( fast && fast->next )   
  6.     {  
  7.         slow = slow->next;  
  8.         fast = fast->next->next;  
  9.         if ( slow == fast ) break;  
  10.     }  
  11.   
  12.     return !(fast == NULL || fast->next == NULL);  
  13. }  

时间复杂度分析:假设甩尾(在环外)长度为 len1(结点个数),环内长度为 len2,链表总长度为n,则n=len1+len2 。当p步长为1,q步长为2时,p指针到达环入口需要len1时间,p到达入口后,q处于哪里不确定,但是肯定在环内,此时p和q开始追赶,q最长需要len2时间就能追上p(p和q都指向环入口),最短需要1步就能追上p(p指向环入口,q指向环入口的前一个节点)。事实上,每经过一步,q和p的距离就拉近一步,因此,经过q和p的距离步就可以追上p。因此总时间复杂度为O(n),n为链表的总长度。


2、分别从链表头和碰撞点,同步地一步一步前进扫描,直到碰撞,此碰撞点即是环的入口。

证明如下:

链表形状类似数字 6 。 

假设甩尾(在环外)长度为 a(结点个数),环内长度为 b 。 

则总长度(也是总结点数)为 a+b 。 

从头开始,0 base 编号。

将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ... 

当 i<a 时,S(i)=i ; 

当 i≥a 时,S(i)=a+(i-a)%b 。

分析追赶过程。 

两个指针分别前进,假定经过 x 步后,碰撞。则有:S(x)=S(2x) 

由环的周期性有:2x=tb+x 。得到 x=tb 。 

另,碰撞时,必须在环内,不可能在甩尾段,有 x>=a 。

连接点为从起点走 a 步,即 S(a)。 

S(a) = S(tb+a) = S(x+a)。 

得到结论:从碰撞点 x 前进 a 步即为连接点。

根据假设易知 S(a-1) 在甩尾段,S(a) 在环上,而 S(x+a) 必然在环上。所以可以发生碰撞。 

而,同为前进 a 步,同为连接点,所以必然发生碰撞。

综上,从 x 点和从起点同步前进,第一个碰撞点就是连接点。

  1. slist* FindLoopPort(slist *head)  
  2. {  
  3.     slist *slow = head, *fast = head;  
  4.   
  5.     while ( fast && fast->next )   
  6.     {  
  7.         slow = slow->next;  
  8.         fast = fast->next->next;  
  9.         if ( slow == fast ) break;  
  10.     }  
  11.   
  12.     if (fast == NULL || fast->next == NULL)  
  13.         return NULL;  
  14.   
  15.     slow = head;  
  16.     while (slow != fast)  
  17.     {  
  18.          slow = slow->next;  
  19.          fast = fast->next;  
  20.     }  
  21.   
  22.     return slow;  
  23. }  

时间复杂度分析:假设甩尾(在环外)长度为 len1(结点个数),环内长度为 len2 。则时间复杂度为“环是否存在的时间复杂度”+O(len1)


3、从碰撞点开始,两个指针p和q,q以一步步长前进,q以两步步长前进,到下次碰撞所经过的操作次数即是环的长度。这很好理解,比如两个运动员A和B从起点开始跑步,A的速度是B的两倍,当A跑玩一圈的时候,B刚好跑完两圈,A和B又同时在起点上。此时A跑的长度即相当于环的长度。

假设甩尾(在环外)长度为 len1(结点个数),环内长度为 len2 ,则时间复杂度为“环是否存在的时间复杂度”+O(len2)。


4、法一:将链表A的尾节点的next指针指向链表B的头结点,从而构造了一个新链表。问题转化为求这个新链表是否有环的问题。

     时间复杂度为环是否存在的时间复杂度,即O(length(A)+length(B)),使用了两个额外指针

     法二:两个链表相交,则从相交的节点起,其后的所有的节点都是都是两个链表共有的。因此,如果它们相交,则最后一个节点一定是共有的。因此,判断两链表相交的方法是:遍历第一个链表,记住最后一个节点。然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交。

     时间复杂度:O(length(A)+length(B)),但是只用了一个额外指针存储最后一个节点


5、将链表A的尾节点的next指针指向链表B的头结点,从而构造了一个环。问题转化为求这个环的入口问题。
时间复杂度:求环入口的时间复杂度


6、分别判断两个链表A、B是否有环(注,两个有环链表相交是指这个环属于两个链表共有)

如果仅有一个有环,则A、B不可能相交

如果两个都有环,则求出A的环入口,判断其是否在B链表上,如果在,则说明A、B相交。

时间复杂度:“环入口问题的时间复杂度”+O(length(B))


7、分别计算出两个链表A、B的长度LA和LB(环的长度和环到入口点长度之和就是链表长度),参照问题3。

如果LA>LB,则链表A指针先走LA-LB,链表B指针再开始走,则两个指针相遇的位置就是相交的第一个节点。

如果LB>LA,则链表B指针先走LB-LA,链表A指针再开始走,则两个指针相遇的位置就是相交的第一个节点。

时间复杂度:O(max(LA,LB))

阅读(1842) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~