首页 > 代码库 > 两个链表相交以及第一个公共节点的问题

两个链表相交以及第一个公共节点的问题

    判读两个链表是否相交以及如果相交它们的第一个公共节点的问题,主要分这么几种情况:

    1)两个链表均不含有环

    2)两个链表均含有环

    对于一个有环一个没有,那么它们即不相交也没有公共节点

    首先定义节点的结构

struct Node{int value;Node *next;};

 判断链表是否有环函数

bool isRingList(Node *head){  if(NULL == head)    return false;  Node *p1 = head, *p2 = p1->next;  while(p2 != NULL && p2->next!=NULL)  {     p1 = p1->next;     p2 = p2->next->next;     if(p1 == p2)         return true;  }  return false;}

  1)两个链表均不含有环

      1.1)判断两个链表是否相交

      对于不含有环的两个链表只要判断它们的tail是否相等就可以决定它们是否相交

bool isCnnNonRingList(Node *h1, Node *h2){  Node *p1, *p2;  while(h1 != NULL)  {    p1 = h1;    h1 = h1->next;  }    while(h2 != NULL)  {    p2 = h2;    h2 = h2->next;  }  return (p1 == p2);}

  1.2)找到它们的第一个公共节点

     对于不含有环的连个链表,只要从头开始缩短长度较长的链表的长度知道长度相等,然后同时移动两个链表,第一个相同节点即为交点

Node* findFirstComNonRingList(Node *h1, Node *h2){   if(!isCnnNonRingList(h1, h2))      return NULL;   Node *p1 = h1, *p2 = h2;   int len1 = NonRingListLen(h1);   int len2 = NonRingListLen(h2);   if(len1 < len2)   {       p1 = h2;       p2 = h1;       len1 = len1 + len2;       len2 = len1 - len2;       len1 = len1 - len2;   }      while(len1 > len2)   {       p1 = p1->next;       len1--;   }   while(p1!=p2 && len1!=0)  {     p1 = p1->next;     p2 = p2->next;   }   return p1;}

  2)对于两个链表均还有环的情况

     这个问题比较复杂了- -,为了简单,我还是先给出求它们公共节点的算法,

     2.1)两个含有环的链表的公共节点

     主要思路是,分别求出,两个含有环链表的环的入口节点,如果他们相等则以它们的入口节点为tail分别计算两个链表的长度,然后就和无环链表的情况一样了。

    

//找到带环链表入口节点函数Node* findEnterRing(Node *head){//判断,head是否带环也不做了:)//这里面涉及到一个运算//从开始,p1每次走一步,p2每次走两步,环的长度r,//第一次相遇时,p1走了s步,p2走了2s步,则//2s = s+n*r,其中n为p2在环内循环的次数,那么,起始点到入口点距离为a,//入口点到第一次相遇点距离为x,则//a+x=s=n*r;//a=(n-1)*r+r-x;//通过这里看以看出,从起始点和相遇点,分别每次走一步,那么它们会在环的入口点相遇//那么,就有了如下求出环入口点的算法  Node *p1 = head, *p2 = head;  do {    p1 = p1->next;    p2 = p2->next;  }while(p1!=p2);  p2 = head;  while(p1!=p2)  {    p1=p1->next;    p2=p2->next;  }  return p1;}Node *findFirstComRingList(Node *h1, Node *h2){//为了简单,判断h1,h2是否有环就不做了吧:)  Node *p1 = findEnterRing(h1);  Node *p2 = findEnterRing(h2);  if(p1 != p2)    return NULL;  int len1 = 1, len2 =1; Node *l1 = h1; while(l1!=p1) {    len1++;    l1= l1->next; }  Node *l2 = h2;  while(l2!=p2)  {    len2++;   l2 = l2->next;  }  l1 = h1;  l2 = h2;  if(len1 < len2)  {     l1=h2;     l2=h1;     len1 = len1+len2;     len2 = len1-len2;     len1 = len1-len2;  }  while(len1 > len2)  {    l1 = l1->next;    len1--;  }  while(l1!=l2 && len1!=0)  {     l1=l1->next;     l2=l2->next;     len1--;  }  return l1;  }

  2.2)两个带环链表相交的问题

    也分两种情况吧

 

 情况1:

   这里贴不了图,可能是浏览器的问题= =就用简图吧

   如果它们的它们的环的入口节点相同,那么可以,分别找到它们的环的入口节点判断是否相等,如果相等则相交,不相等则不想交

  情况2:

  对于相交但是如果节点不相同的情况

 就像这样

  head1:   1->2->3->4->5->6->7->8->4;

  head2:  9->8->4->5->6->7->8;

  具体图像自己脑补吧:),这种情况,我能想到得是,先通过上面的方法找到head1,head2的入口节点,然后,分别让两个入口节点,一个一次前进一步,一个一次前进两步,假设环的长度为r,那么在前进r以后,如果两个节点还没有相遇,那么它们就不在同一个环内,就可以判定它们不想交,如果他们相遇则可以判定两个链表相交,具体代码,自己手补吧:)

两个链表相交以及第一个公共节点的问题