源地址：http://blog.163.com/bbluesnow@126/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取余)

(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。

?

時間復雜度分析：假設甩尾（在環外）長度為 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 點和從起點同步前進，第一個碰撞點就是連接點。

?

?

時間復雜度分析：假設甩尾（在環外）長度為 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））

源碼，并沒有封裝成類，存在某些重復運算：

islistJunction.

?

/******************************************************************************************************
Description?? : 檢查鏈表是否有環
Prototype???? : template<typename T>
????bool checkCircle(T* head)
Input Param?? : head，鏈表的頭結點指針
Output Param? : 無
Return Value? : bool變量，TRUE為有環，FALSE為沒有環
********************************************************************************************************/
template<typename T>
bool 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???? : template<typename T>
????bool isListJunction(T* head1,T* head2)
Input Param?? : head1，第一個鏈表的頭結點；head2，第二個鏈表的頭結點
Output Param? : 無
Return Value? : bool變量，true為有交集，false為沒有交集
********************************************************************************************************/
template<typename T>
bool 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;
?}
?
?// 若都無環，b1==b2==0,尾節點必然相同，是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???? : template<typename T>
????bool isListJunction(T* head1,T* head2)
Input Param?? : head1，第一個鏈表的頭結點；head2，第二個鏈表的頭結點
Output Param? : 無
Return Value? : bool變量，true為有交集，false為沒有交集
********************************************************************************************************/
template<typename T>
bool 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;
?}
?
?// 若都無環，b1==b2==0,尾節點必然相同，是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???? : template<typename T>
????T* findLoopPort(T* head)
Input Param?? : head，鏈表的頭結點
Output Param? : 無
Return Value? : 環入口點的指針
********************************************************************************************************/
template<typename T>
T* 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???? : template<typename T>
????int getLoopLength(T* head)
Input Param?? : head，鏈表的頭結點
Output Param? : 無
Return Value? : int，表示長度
********************************************************************************************************/
template<typename T>
int 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???? : template<typename T>
????int getTailLength(T* head)
Input Param?? : head，鏈表的頭結點
Output Param? : 無
Return Value? : int，表示長度
********************************************************************************************************/
template<typename T>
int getTailLength(T* head)
{
?T* port = findLoopPort(head);
?int length =0;
?T* temp = head;

?while(temp != port)
?{
??length++;
??temp = temp->next;
?}
?return length;
}

main.cpp

#include"isListJunction.h"
#include<string>

template<typename T>
struct 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";

?list<string> firstlist;
?firstlist.push_back(first);
?firstlist.push_back(second);
?firstlist.push_back(three);
?firstlist.push_back(four);
?firstlist.push_back(five);

?list<string> secondlist;
?secondlist.push_back(first2);
?secondlist.push_back(second2);
?secondlist.push_back(four);
?secondlist.push_back(five);

?// 鏈表1，無環
?listNode<string>*head1 =new listNode<string>(first);
?listNode<string>*pnode2 =new listNode<string>(second);
?head1->next= pnode2;
?listNode<string>*pnode3 =new listNode<string>(three);
?pnode2->next= pnode3;
?listNode<string>*pnode4 =new listNode<string>(four);
?pnode3->next= pnode4;
?listNode<string>*pnode5 =new listNode<string>(five);
?pnode4->next= pnode5;

?// 鏈表2，無環
?listNode<string>*head2 =new listNode<string>(first2);
?listNode<string>*pnode22 =new listNode<string>(second2);
?head2->next= pnode22;
?pnode22->next= pnode4;
?pnode4->next= pnode5;

?// 鏈表1、2相交
?bool bJunction = isListJunction(head1,head2);
?std::cout<< bJunction<<std::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，有環
?listNode<string>*head3 =new listNode<string>(first3);
?listNode<string>*pnode32 =new listNode<string>(second3);
?head3->next= pnode32;
?listNode<string>*pnode33 =new listNode<string>(three3);
?pnode32->next= pnode33;
?listNode<string>*pnode34 =new listNode<string>(four3);
?pnode33->next= pnode34;
?listNode<string>*pnode35 =new listNode<string>(five3);
?pnode34->next= pnode35;
?listNode<string>*pnode36 =new listNode<string>(six3);
?pnode35->next= pnode36;
?pnode36->next= pnode33;

?cout<<findLoopPort(head3)->val<<endl;
?cout<<getLoopLength(head3)<<endl;

?// 鏈表4，有環
?listNode<string>*head4 =new listNode<string>(seven3);
?head4->next= pnode32;
?cout<<isListJunction(head3,head4)<<endl;

?cout<<"the length of list3 : "<<getLoopLength(head3)+ getTailLength(head3)<<endl;
?cout<<"the length of list4 : "<<getLoopLength(head4)+ getTailLength(head3)<<endl;
?
?listNode<string>*junctionNode =new listNode<string>;
?cout<<isListJunction(head3,head4,junctionNode)<<endl;
?cout<<"list3 與 list4的交點： "<<junctionNode->val<<endl;
?return0;
}

轉載于:https://www.cnblogs.com/xuhj001/p/3389137.html

總結

以上是生活随笔為你收集整理的转：链表相交问题 详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。