判断两个链表是否相交

题目：给出两个单向链表的头指针，比如h1、h2，
判断链表是否相交，如果不相交返回NULL；如果相交，返回指向第一个相交节点的指针；
时间复杂度控制在O(n)的前提下。
http://blog.163.com/song_0803/blog/static/4609759720120910373784/

  总结：
判断链表存在环的的情况：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<500)
        {
           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;
}