编程之美之判断两个无环链表是否相交

#include

//*************************************
//题目：
//        判断两个无环链表是否相交
//    
//思路：
//        1.判尾法
//            (1)遍历两个链表，记录最后的结点，比较这两个结点；
//            (2)如果这两个结点相同，那么就相交；否则，不相交。
//        2.构环法
//            (1)遍历第一个链表，记下最后一个结点；
//            (2)把该结点的下一个结点设为第二个链表的头结点；
//            (3)检查第二个链表是否形成了环;
//            (4)如果是环，那么就相交；否则，不相交。
//   3.哈希地址法
//            (1)hash编码采用除留余数法。H(key)=key%p;p=11
//            (2)处理冲突采用开放地址法。Hi=(H(key)+di)%m;m=表长
//                                 di=1,2,3……,m-1                
//                    
//                
//*************************************

//
//结点结构
//
struct NODE
{
    char value;
    NODE* next;
};
NODE* Link1;
NODE* Link2;

//
//初始化两个链表
//
void InitLinks()
{
    NODE* p1;
    NODE* p2;
    Link1=(NODE*)malloc(sizeof(NODE));
    Link1->value='10';
    p1=(NODE*)malloc(sizeof(NODE));
    Link1->next=p1;
    p1->value='11';    
    
    Link2=(NODE*)malloc(sizeof(NODE));
    Link2->value='20';
    p2=(NODE*)malloc(sizeof(NODE));
    Link2->next=p2;
    p2->value='21';    

    int count=0;    
    NODE* item=(NODE*)malloc(sizeof(NODE));
    p1->next=item;
    p2->next=item;
    item->value=(char)count;
    NODE* temp=item;
    
    while(count<10)
    {
        count++;
        NODE* s=(NODE*)malloc(sizeof(NODE));
        s->value=(char) count;
        temp->next=s;
        temp=s;
    }
    temp->next=NULL;
}


//
//方法一：判尾法
//
bool IsTailShared(NODE* L1,NODE* L2)
{
    NODE* tail1;
    NODE* tail2;
    NODE* p=L1;
    while(p!=NULL)
    {
        tail1=p;
        p=p->next;
    }
    p=L2;
    while(p!=NULL)
    {
        tail2=p;
        p=p->next;
    }
    if(tail1==tail2)
        return true;
    else
        return false;    
}

//
//方法二：构环法
//
bool IsCycleShared(NODE* L1,NODE* L2)
{
    NODE* tail1;
    NODE* p;
    p=L1;
    while(p!=NULL)
    {
        tail1=p;
        p=p->next;
    }
    tail1->next=L2;

    NODE* t;
    t=L2->next;
    while(t!=L2)
    {
        t=t->next;
        if(t==NULL)
            return false;
    }
    return true;

}


//
//方法三：hash地址法
//蛋疼的方法
bool IsSharedByHash(NODE* L1,NODE* L2)
{
    int Addr[50]; //存放结点的地址

    int count=1;
    int index=1;//指向第i个d[i]

    NODE* Item[20]={NULL};//存放各个结点，m=20

    int d[20];//线性探索

    for(int i=1;i<20;i++)
        d[i]=i;
    NODE* p;
    p=L1;
    Addr[0]=(int)p;
    p=p->next;
    while(p!=NULL)
    {
        Addr[count++]=(int)p;
        p=p->next;
    }
    for(int i=0;i<count;i++)
    {
        Addr[i]=Addr[i]%11;
        int j=1;
        int k=0;
        while(Item[k]!=NULL)
        {
            k=(Addr[i]+d[j++])%20;
        }
        int times=0;
        NODE* t=L1;
        while(times<i)
        {
            t=t->next;
            times++;
        }
        Item[k]=t;
    }

    //
    //开始检查链表2
    //
    p=L2;
    while(p!=NULL)
    {
        int Addr=((int)p)%11;
        int j=1;
        int k=0;
        while(Item[k]!=p)
        {
            k=(Addr+d[j++])%20;
            if(j==20)
                break;
        }
        if(Item[k]==p)
            return true;    
        p=p->next;
    }
    return false;
    
}
int main()
{
    InitLinks();
    if(IsSharedByHash(Link1,Link2))
        printf("OK!");
    else
        printf("NO!");
    return 0;
}