注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

链表求交点  

2014-12-25 22:21:25|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、链表无环判断是否相交
      给定两个单链表(假设链表不存在环),表头分别为 head1 和 head2.判断两个链表是否相交, 如果不相交返回 NULL, 如果相交, 则给出相交的第一个交点。
对题目进行简单分析后不难得出,因为链表的特殊存储结构,使得其在存储结构上如果交叉则一定为“Y”型或者为“V”型,不可能为“X”型。所以相交只需求出第一个交点。
      思路:可以先找到链表p1,p2的最后一个节点(各自遍历),同时记录节点数量a,b;然后判断最后一个节点是否相同,如果不相同则没相交;如果相同,
则从第一个节点和|a-b|+1个节点开始比较看是否相等,不相等都寻找下一个节点直到找到交叉点。
       判断两个链表是否相交有什么用呢?这是因为一旦两个链表出现相交的情况,就可能发生这样的情况,程序释放了链表La的所有节点,这样就导致了另外一个与之有相交节点的链表Lb中的节点也释放了,而Lb的使用者,可能并不知道事实的真相,这会带来很大的麻烦。
       

点击(此处)折叠或打开

  1. Node * list_cross(Node *head1,Node *head2) 
  2. {
  3. int len1=0,len2=0,len=0;
  4. int i=0;
  5. Node *p,*q;
  6. Node *tail1,*tail2;
  7. tail1=NULL;
  8. tail2=NULL;
  9. p=head1;
  10. q=head2;
  11. while(p!=NULL)
  12.     {
  13.         len1++;
  14.         tail1=p;
  15.         p=p->link;
  16.     }
  17. while(q!=NULL)
  18.     {
  19.         len2++;
  20.         tail2=q;
  21.         q=q->link;
  22.     }
  23. if(tail1!=tail2) /// 没有交叉。
  24. return NULL;
  25. p=(len1>=len2?head2:head1);
  26. q=(len1>=len2?head1:head2);
  27. len=abs(len1-len2)+1;
  28.     /// 有交叉。
  29.     while(q!=NULL) /// 将长链表长的一部分走完,之后就能一起走到交点。
  30.     {
  31.     i++;
  32.     if(i==len)
  33.         break;
  34.     q=q->link;
  35.     }
  36.     while( p!=NULL)////此时两个链表等长开始比较。
  37.     {
  38.     if(p!=q)
  39.         {
  40.             p=p->link;
  41.             q=q->link;
  42.         }
  43.     else
  44.         return p;
  45.     }
  46. }

    二、链表有环。
    怎样判断链表中是否存在环,并且找到环的开始节点呢?

  网上有这样的一个解法:设置两个指针fast和slow,初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表),这样就可以判断两个链表是否相交了,程序如下:
bool IsExitsLoop(slist *head)
{
  slist 
*slow = head*fast = head;

  while ( fast && fast->next ) 
  {
    slow 
= slow->next;
    fast 
= fast->next->next;
    if ( slow == fast )

      break;
  }
  return !(fast == NULL || fast->next == NULL);
}

下面看看怎么找环的入口,当fast与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
2s = s + nr
s= nr
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点(从相遇点向后遍历循环回到入口点的距离),于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇点为环入口点,也即为两个链表的第一个相同节点。程序描述如下:

复制代码

点击(此处)折叠或打开

  1. slist* FindLoopPort(slist *head)
  2. {
  3.     slist *slow = head, *fast = head; while ( fast && fast->next ) 
  4.     {
  5.          slow = slow->next;
  6.          fast = fast->next->next; if ( slow == fast ) break;
  7.     } if (fast == NULL || fast->next == NULL) return NULL;
  8.     slow = head; while (slow != fast)
  9.     {
  10.          slow = slow->next;
  11.          fast = fast->next;
  12.     } return slow;
  13. }
  评论这张
 
阅读(564)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018