判断两个链表是否相交

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

Node * list_cross(Node *head1,Node *head2)
{
int len1=0,len2=0,len=0;
int i=0;
Node *p,*q;
Node *tail1,*tail2;
tail1=NULL;
tail2=NULL;
p=head1;
q=head2;
while(p!=NULL)
    {
        len1++;
        tail1=p;
        p=p->link;
    }
while(q!=NULL)
    {
        len2++;
        tail2=q;
        q=q->link;
    }
if(tail1!=tail2) /// 没有交叉。
return NULL;
p=(len1>=len2?head2:head1);
q=(len1>=len2?head1:head2);
len=abs(len1-len2)+1;
    /// 有交叉。
    while(q!=NULL) /// 将长链表长的一部分走完，之后就能一起走到交点。
    {
    i++;
    if(i==len)
        break;
    q=q->link;
    }
    while( p!=NULL)////此时两个链表等长开始比较。
    {
    if(p!=q)
        {
            p=p->link;
            q=q->link;
        }
    else
        return p;
    }
}

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

　　网上有这样的一个解法：设置两个指针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)循环内环+相遇点到环入口点（从相遇点向后遍历循环回到入口点的距离），于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇点为环入口点，也即为两个链表的第一个相同节点。程序描述如下：

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head; while ( fast && fast->next )
    {
         slow = slow->next;
         fast = fast->next->next; if ( slow == fast ) break;
    } if (fast == NULL || fast->next == NULL) return NULL;
    slow = head; while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    } return slow;
}