阿哥论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

新浪微博账号登陆

只需一步,快速开始

搜索
查看: 350|回复: 0

链表经典问题汇总

[复制链接]
 楼主| 发表于 2015-4-9 12:05:09 | 显示全部楼层 |阅读模式
链表经典问题汇总

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

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

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

3、如何知道环的长度

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

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

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

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


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

我们注意到,指针p和q分别以速度为1和2前进。如果以其它速度前进是否可以呢?

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

这样,可以看出,链表有环的充要条件就是某一次循环时,指针p和q的值相等,就是它们相对环中首节点的偏移量相等。我们设环中的结点个数为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-v1为1,则等式成立。

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

[cpp] view plaincopy


  • bool IsExitsLoop(slist *head)  
  • {  
  •     slist *slow = head, *fast = head;  
  •   
  •     while ( fast && fast->next )   
  •     {  
  •         slow = slow->next;  
  •         fast = fast->next->next;  
  •         if ( slow == fast ) break;  
  •     }  
  •   
  •     return !(fast == NULL || fast->next == NULL);  
  • }  

时间复杂度分析:假设甩尾(在环外)长度为 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 点和从起点同步前进,第一个碰撞点就是连接点。

[cpp] view plaincopy


  • slist* FindLoopPort(slist *head)  
  • {  
  •     slist *slow = head, *fast = head;  
  •   
  •     while ( fast && fast->next )   
  •     {  
  •         slow = slow->next;  
  •         fast = fast->next->next;  
  •         if ( slow == fast ) break;  
  •     }  
  •   
  •     if (fast == NULL || fast->next == NULL)  
  •         return NULL;  
  •   
  •     slow = head;  
  •     while (slow != fast)  
  •     {  
  •          slow = slow->next;  
  •          fast = fast->next;  
  •     }  
  •   
  •     return slow;  
  • }  


时间复杂度分析:假设甩尾(在环外)长度为 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))

链表经典问题汇总
摘自:http://blog.csdn.net/vividonly/article/details/6673758
该会员没有填写今日想说内容.
您需要登录后才可以回帖 登录 | 立即注册 新浪微博账号登陆

本版积分规则

快速回复 返回顶部 返回列表