欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

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

struct Node
{
     int m_data;
     Node *m_NextNode;
}

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

   head=node;
   while(head->m_NextNode)
   head=head->m_NextNode;
   while(1)//在鏈尾添加新的節點(diǎn)
 {
    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) //都無(wú)環(huán)
    return isJoinedSimple(h1,h2);
   if((cycle1==0 && cycle2!=0) ||(cycle1!=0 && cycle2==0))//一個(gè)有環(huán)，一個(gè)無(wú)環(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)入口點(diǎn)
Node* pCycle(Node* h, Node* cycle)
{
 Node* p=h;
 while(p!=cycle)
 {
  p=p->m_NextNode;
  cycle=cycle->m_NextNode;
 }
 return p;
}