連続する単一チェーンテーブルが交差しているかどうかを判断し、交差点を見つけます.

チェーンテーブルが交差している場合、2つのチェーンテーブルの形態はYまたはV型であるべきであるため、2つのチェーンテーブルが交差しているかどうかを判断するには2つの方法がある.
一、2つのチェーンテーブルの末尾が同じかどうかを比較し、同じであれば2つのチェーンテーブルが交差し、交差点は2つのチェーンテーブルの長さ差で計算することができる.等しくなるまで別々に遍歴するのが交点の所在です.
 

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;
}

 
二、2つのチェーンテーブルが交差している場合、1つのチェーンテーブルの先頭と末尾を接続すると、2つのチェーンテーブルが一緒になるとリング付きチェーンテーブルが形成され、問題は単一チェーンテーブルにリングがあるかどうかの問題に帰結する.
 

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;
        }
}