免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

  總結：
判斷鏈表存在環(huán)的的情況：int* testCylic(Node *h)
1.若都不存在環(huán),int* isJoinedSimple(Node *h1,Node *h2)
  有交點為“Y”形，最后一個結點相同，abs=a-b，返回第一個相交節(jié)點的指針
2.若存在環(huán)
1).當一個鏈表中有環(huán)，一個鏈表中沒有環(huán)時，兩個鏈表必不相交
2).當兩個鏈表中有環(huán),找出兩個鏈表入環(huán)的第一個結點記為p1,p2
  a.如果p1==p2，說明兩個鏈表在入環(huán)之前或入環(huán)的第一個結點相交；
    則此時可以轉(zhuǎn)為兩個鏈表均不帶環(huán)相交的判斷，把p1，p2當作最后的末尾結點。
 或者從尾節(jié)點開始尋找第一個相交的節(jié)點。
  b.如果p1!=p2，此時兩個鏈表可能完全不相交；也可能兩個鏈表完全共有同一個環(huán)。
    此時，判斷p1->next與p2->next是否相等，如果相等則兩鏈表完全共環(huán)；如果不相等，則完全不相交。

struct Node
{
     int m_data;
     Node *m_NextNode;
}

void InsertNode(&*node)//鏈表尾部插入新的節(jié)點
{
   Node *head;
   Node *newNode;
   int data;

   head=node;
   while(head->m_NextNode)
   head=head->m_NextNode;
   while(1)//在鏈尾添加新的節(jié)點
 {
    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) //都無環(huán)
    return isJoinedSimple(h1,h2);
   if((cycle1==0 && cycle2!=0) ||(cycle1!=0 && cycle2==0))//一個有環(huán)，一個無環(huán)
    return NULL;
   if(cycle1!=0 && cycle2!=0) //都有環(huán)
   {
      Node *pin1=pCycle(h1,cycle1);//環(huán)入口
      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;//完全不同的環(huán)；
       else
             return pin1;//完全相同的環(huán)；

     }
   }
}

//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;
}

//求含有環(huán)形的鏈表的環(huán)入口點
Node* pCycle(Node* h, Node* cycle)
{
 Node* p=h;
 while(p!=cycle)
 {
  p=p->m_NextNode;
  cycle=cycle->m_NextNode;
 }
 return p;
}