微软算法面试(6)：判断俩个链表是否相交

链表假设是单链表，

这题需要找到相交的特征，相交后，最后一个节点肯定相同，所以，如果相同则是相交，否则不相交。

下面看看实现：

#include<iostream>

using namespace std;

struct LNode{
        LNode(int _d = 0):data(_d),next(NULL) {}
        int data;
        LNode* next;
};

bool findInsecNode(LNode* l1, LNode* l2)
{
        if(l1 == NULL) return false;
        if(l2 == NULL) return false;

        LNode* pl1 = l1;
        LNode* pl2 = l2;
        while(pl1->next != NULL)
                pl1 = pl1->next;
        while(pl2->next != NULL)
                pl2 = pl2->next;

        if(pl1 == pl2)
                return true;
        else
                return false;
}

int main()
{
        LNode* L1 = NULL;
        LNode* L2 = NULL;

        LNode n1(1);
        LNode n2(2);
        LNode n3(3);
        LNode n4(4);
        LNode n5(5);
        LNode n6(6);
        L1 = &n1;
        L2 = &n2;

        L1->next = &n3;
        L2->next = &n4;
        L1->next->next = &n5;
        L2->next->next = &n5;

        L1->next->next->next = &n6;
        L2->next->next->next = &n6;

        if(findInsecNode(L1, L2))
                cout << "L1, L2 list is insection" << endl;
        else
                cout << "L1, L2 list is not insection" << endl;
        return 0;
}

输出结果如下：

L1, L2 list is insection

谢谢有点文化的小流氓 网友指出上面有环没法处理，特意加入处理环的逻辑。

再判断相交之前，先判断两个链表是否有环，都没有环，则是上面的实现，都有环，则要判断是否是同一个环，否则不相交。

实现如下：

#include<iostream>

using namespace std;

struct LNode{
        LNode(int _d = 0):data(_d),next(NULL) {}
        int data;
        LNode* next;
};

bool bring(LNode* l)
{
        if(l == NULL || l->next == NULL)
                return false;
        LNode* p1 = l;
        LNode* p2 = l->next;
        while(p2 != NULL && p1 != p2)
        {
                p1 = p1->next;
                if(p2->next != NULL)
                        p2 = p2->next->next;
                else
                        p2 = p2->next;

        }
        if(p2 != NULL)
                return true;
        else
                return false;
}
bool findInsecNode(LNode* l1, LNode* l2)
{
        if(l1 == NULL) return false;
        if(l2 == NULL) return false;

        LNode* pl1 = l1;
        LNode* pl2 = l2;
        if(!bring(l1)&& !bring(l2))
        {
        while(pl1->next != NULL)
                pl1 = pl1->next;
        while(pl2->next != NULL)
                pl2 = pl2->next;

        if(pl1 == pl2)
                return true;
        else

                return false;
        }
        else if(bring(l1) && bring(l2))
        {
                LNode* pll1 = pl1;
                pl1 = pl1->next;
                pll1 = pll1->next->next;

                while(pll1 != pl1)
                {
                        pl1 = pl1->next;
                        pll1 = pll1->next->next;
                }
                LNode* pll2 = pl2;
                pl2 = pl2->next;
                pll2 = pll2->next->next;

                while(pll2 != pl2)
                {
                        pl2 = pl2->next;
                        pll2 = pll2->next->next;
                }
                if(pl1 == pl2) return true;
                LNode* p = pl1;
                p = p->next;
                while(p != pl1)
                {
                        if(p == pl2) return true;
                        p = p->next;
                }
        }
        else
                return false;
}

int main()
{
        LNode* L1 = NULL;
        LNode* L2 = NULL;

        LNode n1(1);
        LNode n2(2);
        LNode n3(3);
        LNode n4(4);

        LNode n5(5);
        LNode n6(6);
        L1 = &n1;
        L2 = &n2;

        L1->next = &n3;
        L2->next = &n4;
        L1->next->next = &n5;
        L2->next->next = &n5;
        L1->next->next->next = &n6;
        L2->next->next->next = &n6;
        L1->next->next->next->next = &n5;

        if(findInsecNode(L1, L2))
                cout << "L1, L2 list is insection" << endl;
        else
                cout << "L1, L2 list is not insection" << endl;
        return 0;
}