给定两个单链表：

1. 如何判断单链表是否交叉？
2. 如何找出出交叉在哪里？
3. 如果可能有环呢？

第二题 2个链表如果都没有环的话，就分别遍历到底 得到第一个长度为m, 第二个长度为n 我们假定m>n;那我们就假定k=m-n;(k>0) 我们开始第三次遍历 从第一个链表的第k+1个节点开始，第二个链表的第1个开始，同时遍历，如果遍历到的2个节点相等， 那么就找到那个交点了。

//判断两链表是否相等
bool isSame(node *h1,node *h2){
    while(p1->next!=NULL){
        p1 = p1->next ;
    }
    while(p2->next!=NULL){
        p2 = p2->next ;
    }
    return p1==p2 ;
}
//判断是否为环形链表，返回回环第一个节点
node *isLoop(node *h){
    node *p = h ,*q = h ;
    if(h==NULL||h->next==NULL){
        return false ;
    }
    do{
        p = p->next ;   //p走一步
        q = q->next->next ; //q走两步
    }while(q->next&&p!=q) ;
    if(p){
        return p ; //p为回环的第一个节点
    }else{
        return NULL ;
    }
}
//判断两链表是否相交
bool isJoined(node *h1,node *h2){
    node *p = isLoop(h1) ;
    node *q = isLoop(h2) ;
    if(p==NULL&&q==NULL){   //两都不是带环链表
        return isSame(h1,h2) ;
    }
    if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL)){ //有一个是带环表
        return false ;
    }
    node *cur = p ;
    while(1){   //两都是带环表，循环判断节点是否相交
        if(cur==q||cur->next==q){
            return true ;
        }
        cur = cur->next->next ;
        p = p->next ;
        if(cur==p){
            return false ;
        }
    }
}

这个是南京摩托罗拉的面试题？

1. 分别遍历两个单链表至尾部，如果尾指针相等那么就交叉，画个图就很好理解的。
2. 两重循环遍历，貌似这个效率低了点，应该有更好的办法，待高手指点。
3. 没看明白，既然都是单链表应该是不会有环的。

2.两个链表“交叉”后的长度一样，如果他们的长度分别为m和n且m>n，第一个链表的指针先向后移动m-n，然后两个链表的指针一起移动就行了，每次移动前看看是不是指向一个地方。

1. 如果两个链表相交，必然是Y字形，所以判断两个链表的最后一个节点是不是相同即可；
2. 根据两个链表的长度差 m-n，长的先走m-n步，短的从头开始走，相遇点即为交点；
3. 先判断两个链表有没有环，如果都没环（已解决），有一个有环一个没环，它们肯定不相交；如果都有环，如何判断？
   a) 从链表1的环里随便找一个节点A（用一快一慢两指针找），看是不是在链表2里，在则相交；不在不交。
   b) 求交点：求出链表1和链表2从头到A的步数，相减，和前面找交点的方法一样处理。