判断两个链表是否相交
题目：给出两个单向链表的头指针，比如h1、h2，
判断链表是否相交，如果不相交返回NULL；如果相交，返回指向第一个相交节点的指针；
时间复杂度控制在O(n)的前提下。
http://blog.163.com/song_0803/blog/static/[***********]3784/
总结：
判断链表存在环的的情况：int* testCylic(Node *h)
1.若都不存在环,int* isJoinedSimple(Node *h1,Node *h2)
有交点为“Y”形，最后一个结点相同，abs=a-b，返回第一个相交节点的指针
2.若存在环
1).当一个链表中有环，一个链表中没有环时，两个链表必不相交
2).当两个链表中有环,找出两个链表入环的第一个结点记为p1,p2
a.如果p1==p2，说明两个链表在入环之前或入环的第一个结点相交；
则此时可以转为两个链表均不带环相交的判断，把p1，p2当作最后的末尾结点。
或者从尾节点开始寻找第一个相交的节点。
b.如果p1!=p2，此时两个链表可能完全不相交；也可能两个链表完全共有同一个环。
此时，判断p1->next与p2->next是否相等，如果相等则两链表完全共环；如果不相等，则完全不相交。
struct Node
{
int m_data;
Node *m_NextNode;
}
void InsertNode(&*node)//链表尾部插入新的节点
{
Node *head;
Node *newNode;
int data;
head=node;
while(head->m_NextNode)
head=head->m_NextNode;
while(1)//在链尾添加新的节点
{
cin>>data;
if(data==0)
break;
newNode=(Node *)malloc(sizeof(Node));
if(!newNode)
exit(ERROR);
//newNode-->m_NextNode=NULL;
head->m_NextNode=newNode;
head=newNode;
head->m_NextNode=NULL;
}
}
// if there could exist cycle
int* isJoin(Node *h1,Node *h2)
{
Node* cycle1=testCylic(h1);
Node* cycle2=testCylic(h2);
if(cycle1==0 && cycle2==0) //都无环
return isJoinedSimple(h1,h2);
if((cycle1==0 && cycle2!=0) ||(cycle1!=0 && cycle2==0))//一个有环，一个无环
return NULL;
if(cycle1!=0 && cycle2!=0) //都有环
{
Node *pin1=pCycle(h1,cycle1);//环入口
Node *pin2=pCycle(h2,cycle2);
if(pin1==pin2)
{
while(pin1==pin2 && pin1>=h1 && pin2>=h2)
{
Node *ptemp=pin1;
pin1--;
pin2--;
}
return ptemp;
}
else
{
int len=0;
while(pin1!=pin2 || len
{
pin2++
}
if(len==500)
return MULL;//完全不同的环；
else
return pin1;//完全相同的环；
}
}
}
//exist cycle?
int* testCylic(Node *h)
{
*Node p1=h;
*Node p2=h;
while(p2!=NULL && p2->m_NextNode!=NULL)
{
p1=p1->m_NextNode;
p2=p2->m_NextNode->m_NextNode;
}
if(p1==p2)
return p1;
else
return NULL;
}
// if there is no cycle.
int* isJoinedSimple(Node *h1,Node *h2)
{
int a=0;
int b=0;
int abs;
Node *p1=h1;
Node *p2=h2;
while(p1->m_NextNode!=NULL)
{
p1=p1->m_NextNode;
a++;
}
while(p2->m_NextNode!=NULL)
{
p2=p2->m_NextNode;
b++
}
if(p1==p2)
abs=a-b;
if(abs>0)
{
p1=h1+abs;
p2=h2;
}
else
{
abs=-abs;
p1=h1;
p2=h2+abs;
}
if(p1!=p2)
{
p1=p1->m_NextNode;
p2=p2->m_NextNode;
}
return p1;
}
//求含有环形的链表的环入口点
Node* pCycle(Node* h, Node* cycle)
{
Node* p=h;
while(p!=cycle)
{
p=p->m_NextNode;
cycle=cycle->m_NextNode;
}
return p;
}