題目

如何判斷兩個有環(huán)單鏈表是否相交？相交的話返回第一個相交的節(jié)點(diǎn)，不想交的話返回空。如果兩個鏈表長度分別為N和M，請做到時間復(fù)雜度O(N+M)，額外空間復(fù)雜度O(1)。
給定兩個鏈表的頭結(jié)點(diǎn)head1和head2，請返回一個bool值代表它們是否相交。

思路

一共有三種相交的情況：

1. 在入環(huán)的節(jié)點(diǎn)相交
2. 在入環(huán)的節(jié)點(diǎn)之前相交
3. 在環(huán)中相交

解題的關(guān)鍵在于先拿到如環(huán)的節(jié)點(diǎn)，然后即可對三種情況進(jìn)行判斷

答案

ListNode* intersectNode(ListNode *head) {
    ListNode *slowNode = head;
    ListNode *fastNode = head;
    while (fastNode->next != NULL && fastNode->next->next != NULL) {
        fastNode = fastNode->next->next;
        slowNode = slowNode->next;
        if (slowNode == fastNode) {
            fastNode = head;
            while (fastNode != slowNode) {
                fastNode = fastNode->next;
                slowNode = slowNode->next;
            }
            return slowNode;
        }
    }
    return NULL;
}

bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
    ListNode *intersectNode1 = intersectNode(head1);
    ListNode *intersectNode2 = intersectNode(head2);
    // 第一種情況：在環(huán)的入口點(diǎn)或者環(huán)入口點(diǎn)之前就已經(jīng)相交
    if (intersectNode1 == intersectNode2) {
        return true;
    }
    // 第二種情況：在環(huán)中相交
    ListNode *current = intersectNode1;
    while (1) {
        current = current->next;
        if (current == intersectNode1) {
            break;
        } else if (current == intersectNode2){
            return true;
        }
    }
    return false;
}