1.用途
判断两个链表是否相交有什么用呢？这是因为一旦两个链表出现相交的情况，就可能发生这样的情况，程序释放了链表La的所有节点，这样就导致了另外一个与之有相交节点的链表Lb中的节点也释放了，而Lb的使用者，可能并不知道事实的真相，这会带来很大的麻烦。
2.问题
看看两个链表相交到底是怎么回事吧，有这样的的几个事实：
（1）一旦两个链表相交，那么两个链表中的节点一定有相同地址。
（2）一旦两个链表相交，那么两个链表从相交节点开始到尾节点一定都是相同的节点。相交指的是结点的地址相同，而不是结点的值相同
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
参考：http://blog.csdn.net/shiren_bod/article/details/6651703
现在讨论一下如何判读一个链表是否有环？
可以这样做，定义两个指针，指向头结点，一个每次移动一个结点，另一个每次移动两个结点，如果慢的能追上快的（也就是两个指针重逢），
就说明有环。
举个例子：就好比跑步，一个跑的快，一个跑的慢，如果跑道是环状的，跑的快就会把跑的慢的扣圈了
如果跑到无环，那么就不会扣圈现象产生 。
快的是慢的一倍速度是不会产生跨越的，如果是2倍，3倍就不一定了。 复杂度不会超过2n， 跑的快的会在慢的跑完一圈之前追上的！
可以参考这个博客：http://blog.csdn.net/lock0812/article/details/2644109
下面是July文章上面的解法：
分析：这是来自编程之美上的微软亚院的一道面试题目。请跟着我的思路步步深入（部分文字引自编程之美）：
- 直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。
- 针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个结点是否在hash表出现，如果所有的第二个链表的结点都能在hash表中找到，即说明第二个链表与第一个链表有相同的结点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？
- 进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断俩个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。
所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O（N），空间复杂度为O（1），显然比解法三更胜一筹。 - 上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?还能找到最后一个结点进行判断么?上面的方法还同样有效么?显然，这个问题的本质已经转化为判断链表是否有环。那么，如何来判断链表是否有环呢?
总结：
所以，事实上，这个判断两个链表是否相交的问题就转化成了：
1.先判断带不带环
2.如果都不带环，就判断尾节点是否相等
3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。
下面先给出是否有环的算法，就使用前面我的文章中的方法，但是题目的需要，增加了保存了尾节点。
算法和July的方法是一样的，但是实现的方式有点不同而已。
- //判断链表是否有环
- bool IsLoop(node *head, node **firstLoop, node **lastNode)
- {
- node *first = head;
- node *second = head;
- if(NULL == head || NULL == head->next)
- {
- return false;
- }
- do
- {
- first = first->next; //first走一步
- second = second->next->next; //second走两步
- }while(second && second->next && first != second);
- if(first == second)
- {
- *firstLoop = first; //保存环的首节点
- return true;
- }
- else
- {
- *lastNode = first->next; //保存尾节点
- //printf("%d\n", first->next->data);
- return false;
- }
- return false;
- }
接下来是判断是否相交的算法，和July的代码是一样的，只是自己写了一遍。学习了.....
- //判断两链表是否相交
- //1.如果都不带环，就判断尾节点是否相等
- //2.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
- bool IsCross(node *head1, node *head2)
- {
- node *firstLoop1 = NULL;
- node *firstLoop2 = NULL;
- node *lastNode1 = NULL;
- node *lastNode2 = NULL;
- if(NULL == head1 || NULL == head2)
- {
- printf("Link is Empty!\n");
- exit(1);
- }
- bool isLoop1 = IsLoop(head1, &firstLoop1, &lastNode1);
- bool isLoop2 = IsLoop(head2, &firstLoop2, &lastNode2);
- if(!isLoop1 && !isLoop2) //两个都无环
- {
- return (lastNode1 == lastNode2);
- }
- else if(isLoop1 != isLoop2) //一个有环，另一个无环
- {
- return false;
- }
- else //两个都有环，判断环里的节点是否能到达另一个链表环里的节点
- {
- node *temp = firstLoop1->next;
- while(temp != firstLoop1)
- {
- if(temp == firstLoop2) //判断第二个链表里的环节点是否在第一个链表中
- return true;
- temp = temp->next;
- }
- }
- return false;
- }
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)
{
int isLoop=0;
LinkList *fast,*slow;
fast=list;
slow=list;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;//fast每次两步，slow每次一步
if(fast==slow) //当两指针相等时，判断链表中有环
{
isLoop=1;
break;
}
}
if(isLoop==1)//链表中有环时
{
slow=list;
while(slow!=fast)//一个头指针，一个相遇点指针，两个第一次相等时为环入口点
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
else
{
cout<<"链表中没有环";
return NULL;
}
}
http://blog.163.com/bbluesnow@126/blog/static/27784545201251051156817/