第7题
微软亚院之编程
判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展:
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
思路：
判断两个链表是否相交，并且求第一个节点列（无环）。
利用计数
如果两个链表相交，两个链表就会有共同的结点列；统计链表的长度，求两个链表长度差（目的是将两个链表变成到末尾长度相同的两个链表，相交部分一定在里面），然后往后遍历，找到相等的结点，就是第一个结点。
判断是否有环
可以设置两个指针(fast,slow)，初始值均指向头，slow每次向前一步，fast每次向前两步；如果链表中有环，则fast先进入环中，而slow后进入环中，两个指针在环中必定相遇;如果fast遍历到尾部为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)=s为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点
因而，可以在链表头，相遇点分别设定一个指针，每次各走一步，两个指针必定相遇，则相遇第一点为环入口点。
带有环的链表是否相交
（1）将有环的链表分成两个链表，一个是环段，一个是到环的入口（包括入口点）。
（2）比较无环的那一段。方法和比较无环链表一样。
下面代码给出了判断是否有环，以及环的入口点查找，如果查找为NULL，说明无环；如果有环，可以写一个函数将链表从环断开（此函数未给出）。
#include<cstdio> #include<malloc.h> #include<iostream> using namespace std; struct node{ int m_nValue; List *next; }; void InsertList(node *&head,int value){ if(head==NULL){ List *m_pList=new List(); if(m_pList==NULL){ cout<<"insufficient memory. "; return; } m_pList->m_nValue=value; m_pList->next=NULL; head=m_pList; }else InsertList(head->next,value); }
//查找相交点 node* FindNode(node *head1,node *head2){ if(head1==NULL||head2==NULL) return NULL;//如果为空，一定不能相交 node *p1,*p2; p1=head1;p2=head2; int len1=0,len2=0; int diff=0;//通过计数法统计他们的长度差 while(p1->next!=NULL){ p1=p1->next;len1++; } while(p2->next!=NULL){ p2=p2->next;len2++; } if(p1!=p2) return NULL;//最后一个结点不同，肯定不相交 diff=len1>len2?len1-len2:len2-len1; if(len1>len2){p1=head1;p2=head2;} else {p1=head2;p2=head1;} for(int i=0;i<diff;i++) p1=p1->next; while(p1!=p2){ p1=p1->next;p2=p2->next; } return p2; } node* HasLoop(node *head){ bool hasLoop = false; node *fast,*slow;//利用快慢指针 fast=head;slow=head; while(fast&&fast->next){ slow=slow->next; fast=fast->next->next;//fast每次走两步，slow每次走一步 if(fast==slow){//当两指针相遇，说明有环 hasLoop =true; break; } } if(hasLoop){//有环时我们找入环的第一个结点 slow=head; while(slow!=fast){ slow=slow->next; fast=fast->next; }
//可以将链表的分解函数在这里调用。将slow设为标志，无环的新链表为表头到slow。slow->next=NULL;
return slow;
}else return NULL; }