微軟等數據結構與算法面試100題 第七題

第七題

微軟亞院之編程判斷倆個鏈表是否相交
給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。
為了簡化問題，我們假設倆個鏈表均不帶環。
問題擴展：
1.如果鏈表可能有環列?
2.如果需要求出倆個鏈表相交的第一個節點列?

 實現代碼：
[cpp]
#include<iostream> 
 
using namespace std; 
 
struct linkNode 
{ 
    linkNode * nextLinkNode; 
 
    float value; 
}; 
bool check2LinkList(linkNode * head1, linkNode * head2) 
{ 
     
 
    bool boolRingList1 = false; 
    bool boolRingList2 = false; 
    bool boolMutual = false; 
 
    //判斷是否存在環 
    linkNode * tempLinkNode1 = head1; 
    linkNode * tempLinkNode2 = head1; 
 
    while(NULL!=tempLinkNode2) 
    { 
        tempLinkNode1 = tempLinkNode1->nextLinkNode; 
        tempLinkNode2 = tempLinkNode2->nextLinkNode; 
        if(NULL!=tempLinkNode2&&NULL!=tempLinkNode2->nextLinkNode)tempLinkNode2 = tempLinkNode2 ->nextLinkNode; 
        if(tempLinkNode1==tempLinkNode2) 
        { 
            boolRingList1 = true; 
            break; 
        } 
    } 
    tempLinkNode1 = head2; 
    tempLinkNode2 = head2; 
    while(NULL!=tempLinkNode2->nextLinkNode) 
    { 
        tempLinkNode1 = tempLinkNode1->nextLinkNode; 
        tempLinkNode2 = tempLinkNode2->nextLinkNode; 
        if(NULL!=tempLinkNode2&&NULL!=tempLinkNode2->nextLinkNode)tempLinkNode2 = tempLinkNode2 ->nextLinkNode; 
        if(tempLinkNode1==tempLinkNode2) 
        { 
            boolRingList2 = true; 
            break; 
        } 
    } 
 
    if(boolRingList1&&boolRingList2) 
    { 
        //都存在環 
        //cout<<"both have ring"<<endl; 
        int nodeMaxNum = 100; 
        int testStart = 0; 
        tempLinkNode1 = head1; 
        tempLinkNode2 = head2; 
        while(testStart<nodeMaxNum) 
        { 
            tempLinkNode1 = tempLinkNode1 ->nextLinkNode; 
            tempLinkNode2 = tempLinkNode2 ->nextLinkNode->nextLinkNode; 
            if(tempLinkNode1==tempLinkNode2) 
            { 
                boolMutual = true; 
                cout<<"存在環，有交點"<<endl; 
                break; 
            } 
 
             
        } 
 
    } 
    else if(boolRingList1||boolRingList2) 
    { 
        //一個存在環 一個不存在環 
        cout<<"一個存在環，木有交點"<<endl; 
    } 
    else 
    { 
        //不存在環 終點相同 
        tempLinkNode1 = head1; 
        tempLinkNode2 = head2; 
        while(NULL!=tempLinkNode1->nextLinkNode) 
            tempLinkNode1 = tempLinkNode1 ->nextLinkNode; 
        while(NULL!=tempLinkNode2->nextLinkNode) 
            tempLinkNode2 = tempLinkNode2 ->nextLinkNode; 
        if(tempLinkNode1==tempLinkNode2) 
        { 
            boolMutual = true; 
            cout<<"不存在環，有交點"<<endl; 
        } 
     
    } 
 
 
    return boolMutual; 
 
 
} 
int main() 
{ 
 
    #pragma region //構建測試鏈表 head1 head2 head3 head4 head5 
    // head1 與 head2 都不存在環 但存在相交  
    // head3 與 head4 存在環 存在相交 
    // head3 與 head1: head3存在環 head1 不存在環 不相交 
    // head3 與 head5: head3存在環 
    // 
    // 
    linkNode *head1 = new struct linkNode(); 
    linkNode *b = new struct linkNode(); 
    linkNode *c = new struct linkNode(); 
    linkNode *d = new struct linkNode(); 
    linkNode *e = new struct linkNode(); 
     
 
    head1->nextLinkNode = b; 
    head1->value = 0; 
    b->nextLinkNode = c; 
    b->value = 1; 
    c->nextLinkNode = d; 
    c->value = 2; 
    d->nextLinkNode = e; 
    d->value = 3; 
    e->nextLinkNode = NULL; 
    e->value = 4; 
 
    linkNode * temp = head1; 
    while(NULL != temp) 
    { 
        cout<<temp->value<<" "; 
        temp = temp->nextLinkNode; 
         
    } 
 
    cout<<endl; 
 
    linkNode *head2 = new struct linkNode(); 
    linkNode *i = new struct linkNode(); 
    linkNode *j = new struct linkNode(); 
    linkNode *k = new struct linkNode(); 
    linkNode *l = new struct linkNode(); 
 
    head2->nextLinkNode = i; 
    head2->value = 10; 
    i->nextLinkNode = j; 
    i->value = 11; 
    j->nextLinkNode = head1; 
    j->value = 12; 
 
    linkNode *head3 = new struct linkNode(); 
    linkNode *m = new struct linkNode(); 
    linkNode *n = new struct linkNode(); 
    linkNode *o = new struct linkNode(); 
    linkNode *p = new struct linkNode(); 
 
    head3->nextLinkNode = m; 
    head3->value =21; 
    m->nextLinkNode = n; 
    m->value = 22; 
    n->nextLinkNode = o; 
    n->value = 23; 
    o->nextLinkNode = p; 
    o->value = 24; 
    p->nextLinkNode = n; 
    p->value = 25; 
 
    linkNode *head4 = new struct linkNode(); 
    head4 ->nextLinkNode = o; 
    head4 ->value = 31; 
 
        temp = head1; 
    int maxNum =20; 
    int tempindex = 0; 
    while(NULL != temp&&tempindex < maxNum) 
    { 
        tempindex = tempindex + 1; 
        cout<<temp->value<<" "; 
        temp = temp->nextLinkNode;    
    } 
    cout<<endl; 
    temp = head2; maxNum =20;tempindex = 0; 
    while(NULL != temp&&tempindex < maxNum) 
    { 
        tempindex = tempindex + 1; 
        cout<<temp->value<<" "; 
        temp = temp->nextLinkNode;    
    } 
    cout<<endl; 
    temp = head3; maxNum =20;tempindex = 0; 
    while(NULL != temp&&tempindex < maxNum) 
    { 
        tempindex = tempindex + 1; 
        cout<<temp->value<<" "; 
        temp = temp->nextLinkNode;    
    } 
    cout<<endl; 
    temp = head4; maxNum =20;tempindex = 0; 
    while(NULL != temp&&tempindex < maxNum) 
    { 
        tempindex = tempindex + 1; 
        cout<<temp->value<<" "; 
        temp = temp->nextLinkNode;    
    } 
    cout<<endl; 
    #pragma endregion 
 
 
    check2LinkList(head1,head2); 
    check2LinkList(head1,head3); 
    check2LinkList(head3,head4); 
    return 0; 
}