辽宁省住房和城乡建设厅网站换了,旅游系统,什么行业必须做网站,龙岩网站建设公司源地址#xff1a;http://blog.163.com/bbluesnow126/blog/static/27784545201251051156817/ 链表相交问题 2012-06-10 17:15:37| 分类#xff1a; 算法 | 标签#xff1a;微软面试题 |字号 订阅 1、如何判断一个单链表有环 2、如何判断一个环的入口点在哪里 3、如何知… 源地址http://blog.163.com/bbluesnow126/blog/static/27784545201251051156817/ 链表相交问题 2012-06-10 17:15:37| 分类 算法 | 标签微软面试题 |字号 订阅 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取余) (am*v1)mod(n) (bm*v2) mod(n) 设等式左边mod(n)的最大整数为k1等式右边mod(n)的最大整数为k2则 (am*v1)-k1*n (bm*v2)-k2*n 整理以上等式 m |((k2-k1)*na-b)/( v2-v1)| ① 如果是等式①成立就要使循环次数m为一整数。显然如果v2-v1为1则等式成立。 这样p和q分别以速度为v1和v2且|v2-v1|为1时按以上算法就可找出链表中是否有环。当然|v2-v1|不为1时也可能可以得出符合条件的m。 时间复杂度分析假设甩尾在环外长度为 len1结点个数环内长度为 len2链表总长度为n则nlen1len2。当p步长为1q步长为2时p指针到达环入口需要len1时间p到达入口后q处于哪里不确定但是肯定在环内此时p和q开始追赶q最长需要len2时间就能追上pp和q都指向环入口最短需要1步就能追上pp指向环入口q指向环入口的前一个节点。事实上每经过一步q和p的距离就拉近一步因此经过q和p的距离步就可以追上p。因此总时间复杂度为O(n)n为链表的总长度。 2、分别从链表头和碰撞点同步地一步一步前进扫描直到碰撞此碰撞点即是环的入口。 证明如下 链表形状类似数字 6 。 假设甩尾在环外长度为 a结点个数环内长度为 b 。 则总长度也是总结点数为 ab 。 从头开始0 base 编号。 将第 i 步访问的结点用 S(i) 表示。i 0, 1 ... 当 ia 时S(i)i 当 i≥a 时S(i)a(i-a)%b 。 分析追赶过程。 两个指针分别前进假定经过 x 步后碰撞。则有S(x)S(2x) 由环的周期性有2xtbx 。得到 xtb 。 另碰撞时必须在环内不可能在甩尾段有 xa 。 连接点为从起点走 a 步即 S(a)。 S(a) S(tba) S(xa)。 得到结论从碰撞点 x 前进 a 步即为连接点。 根据假设易知 S(a-1) 在甩尾段S(a) 在环上而 S(xa) 必然在环上。所以可以发生碰撞。 而同为前进 a 步同为连接点所以必然发生碰撞。 综上从 x 点和从起点同步前进第一个碰撞点就是连接点。 时间复杂度分析假设甩尾在环外长度为 len1结点个数环内长度为 len2 。则时间复杂度为“环是否存在的时间复杂度”Olen1 3、从碰撞点开始两个指针p和qq以一步步长前进q以两步步长前进到下次碰撞所经过的操作次数即是环的长度。这很好理解比如两个运动员A和B从起点开始跑步A的速度是B的两倍当A跑玩一圈的时候B刚好跑完两圈A和B又同时在起点上。此时A跑的长度即相当于环的长度。 假设甩尾在环外长度为 len1结点个数环内长度为 len2 则时间复杂度为“环是否存在的时间复杂度”O(len2)。 4、法一将链表A的尾节点的next指针指向链表B的头结点从而构造了一个新链表。问题转化为求这个新链表是否有环的问题。 时间复杂度为环是否存在的时间复杂度即Olength(A)length(B)使用了两个额外指针 法二两个链表相交则从相交的节点起其后的所有的节点都是都是两个链表共有的。因此如果它们相交则最后一个节点一定是共有的。因此判断两链表相交的方法是遍历第一个链表记住最后一个节点。然后遍历第二个链表到最后一个节点时和第一个链表的最后一个节点做比较如果相同则相交。 时间复杂度Olength(A)length(B)但是只用了一个额外指针存储最后一个节点 5、将链表A的尾节点的next指针指向链表B的头结点从而构造了一个环。问题转化为求这个环的入口问题。时间复杂度求环入口的时间复杂度 6、分别判断两个链表A、B是否有环注两个有环链表相交是指这个环属于两个链表共有 如果仅有一个有环则A、B不可能相交 如果两个都有环则求出A的环入口判断其是否在B链表上如果在则说明A、B相交。 时间复杂度“环入口问题的时间复杂度”OlengthB 7、分别计算出两个链表A、B的长度LA和LB环的长度和环到入口点长度之和就是链表长度参照问题3。 如果LALB则链表A指针先走LA-LB链表B指针再开始走则两个指针相遇的位置就是相交的第一个节点。 如果LBLA则链表B指针先走LB-LA链表A指针再开始走则两个指针相遇的位置就是相交的第一个节点。 时间复杂度OmaxLA,LB 源码并没有封装成类存在某些重复运算 islistJunction. /******************************************************************************************************Description : 检查链表是否有环Prototype : templatetypename T bool checkCircle(T* head)Input Param : head链表的头结点指针Output Param : 无Return Value : bool变量TRUE为有环FALSE为没有环********************************************************************************************************/templatetypename Tbool checkCircle(T* head){ if(NULL head) returnfalse; T* low head; T* fast head; while(low-next! NULL (fast-next! NULL)(fast-next)-next! NULL) { low low-next; fast (fast-next)-next; if(low fast) { returntrue; } } returnfalse;} /******************************************************************************************************Description : 判断两个链表是否相交Prototype : templatetypename T bool isListJunction(T* head1,T* head2)Input Param : head1第一个链表的头结点head2第二个链表的头结点Output Param : 无Return Value : bool变量true为有交集false为没有交集********************************************************************************************************/templatetypename Tbool isListJunction(T* head1,T* head2){ if(NULL head1 || NULL head2) { returnfalse; } // 如果头结点相同代表相同的链表肯定是相交 if(head1 head2) { returntrue; } // 检测是否有环 bool b1 checkCircle(head1); bool b2 checkCircle(head2); // 若相交则两个链表要么都无环要么都有环 if(b1 ! b2) { returnfalse; } // 若都无环b1b20,尾节点必然相同是Y字形 if(!b1) { while(head1 ! NULL) { head1 head1-next; } while(head2 ! NULL) { head2 head2-next; } if(head1 head2) { returntrue; } } // 若有环则找出链表1的环入口看是否在链表2上 if(b1) { T* port findLoopPort(head1); if(port ! NULL) { T* temp head2; int length2 getLoopLength(head2) getTailLength(head2); while(port ! temp (length2--)0) temp temp-next; if(port temp) returntrue; else returnfalse; } } returnfalse;} /******************************************************************************************************Description : 判断两个链表是否相交Prototype : templatetypename T bool isListJunction(T* head1,T* head2)Input Param : head1第一个链表的头结点head2第二个链表的头结点Output Param : 无Return Value : bool变量true为有交集false为没有交集********************************************************************************************************/templatetypename Tbool isListJunction(T* head1,T* head2,T *junctionNode){ if(NULL head1 || NULL head2) { returnfalse; } // 如果头结点相同代表相同的链表肯定是相交 if(head1 head2) { junctionNode head1; returntrue; } // 检测是否有环 bool b1 checkCircle(head1); bool b2 checkCircle(head2); // 若相交则两个链表要么都无环要么都有环 if(b1 ! b2) { returnfalse; } // 若都无环b1b20,尾节点必然相同是Y字形 if(!b1) { T* node1 head1; T* node2 head2; while(node1 ! NULL) { node1 node1-next; } while(node2 ! NULL) { node2 node2-next; } if(node1 node2) { // 相交把第一个链表的尾节点指向第二个链表 node1-next head2; junctionNode findLoopPort(head1); returntrue; } } // 若有环则找出链表1的环入口看是否在链表2上 if(b1) { int length1 getLoopLength(head1) getTailLength(head1); int length2 getLoopLength(head2) getTailLength(head2); int len length2; T* port findLoopPort(head1); if(port ! NULL) { T* temp head2; while(port ! temp (len--)0) temp temp-next; if(port temp) { // 若长度相等同步寻找相同的节点 if(length1 length2) { while(head1 ! head2) { head1 head1-next; head2 head2-next; } junctionNode head1; } // 若长度不等长的先剪掉长度差然后再同步递增 elseif(length1 length2) { int step length1 - length2; while(step--) { head1 head1-next; } while(head1 ! head2) { head1 head1-next; head2 head2-next; } junctionNode head1; } else { int step length2 - length1; while(step--) { head2 head2-next; } while(head1 ! head2) { head1 head1-next; head2 head2-next; } junctionNode head1; } returntrue; } else { returnfalse; } } } returnfalse;} /******************************************************************************************************Description : 查找环的入口Prototype : templatetypename T T* findLoopPort(T* head)Input Param : head链表的头结点Output Param : 无Return Value : 环入口点的指针********************************************************************************************************/templatetypename TT* findLoopPort(T* head){ // 判断是否有环五环返回NULL checkCircle(head); if(!checkCircle(head)) return NULL; T* low head; T* fast head; // low按照步长1增加fast按照步长2增加找到碰撞点 while(1) { low low-next; fast fast-next-next; if(low fast) break; } // 分别从头结点和碰撞节点开始按照步长1增加遍历链表第一个节点相同的点是环入口点 low head; while(low ! fast) { low low-next; fast fast-next; } return low; } /******************************************************************************************************Description : 计算环的长度Prototype : templatetypename T int getLoopLength(T* head)Input Param : head链表的头结点Output Param : 无Return Value : int表示长度********************************************************************************************************/templatetypename Tint getLoopLength(T* head){ if(!checkCircle(head)) return0; T* low head; T* fast head; int length 0; // low按照步长1增加fast按照步长2增加找到碰撞点,然后接着循环直到下一次碰撞 // 计算两次碰撞之间的循环次数即为长度 while(1) { low low-next; fast fast-next-next; if(low fast) break; } while(1) { low low-next; fast fast-next-next; length; if(low fast) break; } return length;} /******************************************************************************************************Description : 计算有环链表的尾长度Prototype : templatetypename T int getTailLength(T* head)Input Param : head链表的头结点Output Param : 无Return Value : int表示长度********************************************************************************************************/templatetypename Tint getTailLength(T* head){ T* port findLoopPort(head); int length 0; T* temp head; while(temp ! port) { length; temp temp-next; } return length;} main.cpp #includeisListJunction.h#includestring templatetypename Tstruct listNode{ T val; listNode *pre; listNode *next; listNode() { pre NULL; next NULL; } listNode(T value) { val value; pre NULL; next NULL; }}; int main(int argc,char** argv){ string first my is; string second your; string three is; string four king; string five name; string first2 speak; string second2 what; liststring firstlist; firstlist.push_back(first); firstlist.push_back(second); firstlist.push_back(three); firstlist.push_back(four); firstlist.push_back(five); liststring secondlist; secondlist.push_back(first2); secondlist.push_back(second2); secondlist.push_back(four); secondlist.push_back(five); // 链表1无环 listNodestring*head1 new listNodestring(first); listNodestring*pnode2 new listNodestring(second); head1-next pnode2; listNodestring*pnode3 new listNodestring(three); pnode2-next pnode3; listNodestring*pnode4 new listNodestring(four); pnode3-next pnode4; listNodestring*pnode5 new listNodestring(five); pnode4-next pnode5; // 链表2无环 listNodestring*head2 new listNodestring(first2); listNodestring*pnode22 new listNodestring(second2); head2-next pnode22; pnode22-next pnode4; pnode4-next pnode5; // 链表1、2相交 bool bJunction isListJunction(head1,head2); std::cout bJunctionstd::endl; std::cout checkCircle(head1)endl; std::cout checkCircle(head2)endl; string first3 1; string second3 2; string three3 3; string four3 4; string five3 5; string six3 6; string seven3 7; // 链表3有环 listNodestring*head3 new listNodestring(first3); listNodestring*pnode32 new listNodestring(second3); head3-next pnode32; listNodestring*pnode33 new listNodestring(three3); pnode32-next pnode33; listNodestring*pnode34 new listNodestring(four3); pnode33-next pnode34; listNodestring*pnode35 new listNodestring(five3); pnode34-next pnode35; listNodestring*pnode36 new listNodestring(six3); pnode35-next pnode36; pnode36-next pnode33; coutfindLoopPort(head3)-valendl; coutgetLoopLength(head3)endl; // 链表4有环 listNodestring*head4 new listNodestring(seven3); head4-next pnode32; coutisListJunction(head3,head4)endl; coutthe length of list3 : getLoopLength(head3) getTailLength(head3)endl; coutthe length of list4 : getLoopLength(head4) getTailLength(head3)endl; listNodestring*junctionNode new listNodestring; coutisListJunction(head3,head4,junctionNode)endl; coutlist3 与 list4的交点 junctionNode-valendl; return0;} 转载于:https://www.cnblogs.com/xuhj001/p/3389137.html
