《程式設計之美》兩連結清單相交及擴充詳解

 《程式設計之美》兩連結清單相交及擴充詳解：

給定一個單連結清單，隻給出頭指針h：

1、如何判斷是否存在環？

2、如何知道環的長度？

3、如何找出環的連接配接點在哪裡？

4、帶環連結清單的長度是多少？ 

解法：

1、對于問題1，使用追趕的方法，設定兩個指針slow、fast，從頭指針開始，每次分别前進1步、2步。如存在環，則兩者相遇；如不存在環，fast遇到NULL退出。

2、對于問題2，記錄下問題1的碰撞點p，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度s。

3、問題3：有定理：碰撞點p到連接配接點的距離=頭指針到連接配接點的距離，是以，分别從碰撞點、頭指針開始走，相遇的那個點就是連接配接點。

設h走到c的長度為a，s走到p的長度為b，p走到的s長度為c。則相當于2個人從h節點開始，分别以1和2的速度走，相遇點為p，則第一個人走的時間為h->s->p的時間(a+b），第二個人在該時間内走的距離則為2(a+b)，而它走的路線為h->s->p->s->p，即比第一個人多走了一個環的長度，距離為(a+b+c+b)。則由2(a+b)= (a+b+c+b)，可得a=c，即ps=hs，即證。

4、問題3中已經求出連接配接點距離頭指針的長度，加上問題2中求出的環的長度，二者之和就是帶環單連結清單的長度。

判斷是否存在環的程式：

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); 

} 

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);

}

尋找環連接配接點（入口點）的程式：

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; 

}

《程式設計之美》裡面有一篇是講如何判斷兩連結清單是否相交，讀後覺得原文太過啰嗦。于是，筆者總結了一下，此類問題可以擴充為兩大類，分别是：

1、單連結清單與環問題http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx

2、單連結清單相交與環問題（本文）

--------------------------------------------------------------------------------

給定兩單連結清單A、B，隻給出兩頭指針。請問：

1、如何判斷兩單連結清單（無環）是否相交？

有兩種可取的辦法：

（1）人為構環，将連結清單A的尾節點指向連結清單B，再判斷是否構環成功？從連結清單B的頭指針往下周遊，如果能夠回到B，則說明相交

（2）判斷兩連結清單最後一個節點是否相同，如果相交，則尾節點肯定是同一節點

2、如何判斷兩單連結清單（不知是否有環）相交？

先判斷是否有環，判斷是否有環可以使用追逐辦法，設定兩個指針，一個走一步，一個走兩步，如果能相遇則說明存在環

（1）兩個都沒環：回到問題1

（2）一個有環，一個沒環：不用判斷了，肯定兩連結清單不相交

（3）兩個都有環：判斷連結清單A的碰撞點是否出現在連結清單B的環中，如果在，則相交。（相交時，環必定是兩連結清單共有的）

3、如何尋找兩相交連結清單（不知是否有環）的第一個相交節點？

同樣，使用追逐辦法先判斷是否存在環，分情況讨論

（1）無環：人為構環，将連結清單A的尾節點指向連結清單B，則構成一個帶環的單連結清單。這個問題就轉換成尋找帶環單連結清單的環入口節點。

    解法參考：http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx

（2）有環：計算出兩連結清單的長度lA、lB，（環的長度和環到入口點長度之和就是連結清單長度）

計算帶環連結清單長度，可參考http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx

如果lA>lB，則連結清單A指針先走lA-lB，然後連結清單B指針開始走，兩者相遇的點就是相交點

如果lB>lA，則連結清單B指針先走lB-lA，然後連結清單A指針開始走，兩者相遇的點就是相交點