学步园

链表如果相交则两个链表的形态应该是Y或者是V型，所以判断两个链表是否相交有两种方式：

一、比较两个链表的尾部是否相同，如果相同则两个链表相交，交叉点可以通过两个链表的长度差进行计算，因为交点后面的长度是相同的，差值是交点前形成的，可以分别设定两个指针，长的链表先遍历到差值的位置，短的链表指向头部，分别遍历直到相等就是交点的所在。

int IsCross(ListNode *p, ListNode *q){
        if(p == NULL || q == NULL){
                return 0;
        }
        ListNode *node1 = NULL;
        ListNode *node2 = NULL;
        while(p != NULL){
                node1 = p;
                p = p->next;
        }
        while(q != NULL){
                node2 = q;
                q = q->next;
        }
        if(node1 == node2){
                return 1;
        }else{
                return 0;
        }
}

寻找交点：

ListNode *FindNode(ListNode *p, ListNode *q){
        if(p == NULL || q == NULL){
                return NULL;
        }
        ListNode *node1 = p;
        ListNode *node2 = q;
        int len1 =  0, len2 = 0;
        while(node1 != NULL){
                node1 = node->next;
                len1++;
        }
        while(node2 != NULL){
                node2 = node2->next;
                len2++;
        }
        int len = len1 > len2 ? len1 - len2 : len2 -len1;
        ListNode *lenNode = len1 > len2 ? p : q;
        ListNode *shortNode = len1 < len2 ? p : q;
        for(int i = 0; i < len + 1;i++){
                lenNode = lenNode->next;
        }
        while(shortNode != NULL && lenNode != NULL && shortNode != lenNode){
                shortNode = shortNode->next;
                lenNode = lenNode->next;
        }
        return shortNode;
}

二、如果两个链表相交，那么如果将一个链表的首尾相连，那么两个链表和在一起就会形成一个有环的链表，问题就归结到单链表是否有环的问题：

int IsCross(ListNode *p, ListNode *q){
        if(p == NULL || q == NULL){
                return 0;
        }
        ListNode *t = p;
        while(t->next != NULL){
                t = t->next;
        }
        t->next = p;
        ListNode *fast = q;
        ListNode *slow = q;
        while(fast != NULL && fast->next != NULL){
                fast = fast->next->next;
                slow = slow->next;
                if(fast == slow){
                        break;
                }
        }
        if(fast != NULL && fast->next != NULL){
                return 1;
        }else{
                return 0;
        }
}