問題定義

給定兩個無環單鏈表頭指針 head1、head2，判斷是否相交（存在共同節點，**地址相同** 而非值相同）。

方案對比

方案一：暴力法

bool intersectBrute(ListNode* h1, ListNode* h2) {
    for (auto* p1 = h1; p1; p1 = p1->next)
        for (auto* p2 = h2; p2; p2 = p2->next)
            if (p1 == p2) return true;
    return false;
}

方案二：哈希表

bool intersectHash(ListNode* h1, ListNode* h2) {
    std::unordered_set<ListNode*> vis;
    for (auto* p = h1; p; p = p->next) vis.insert(p);
    for (auto* p = h2; p; p = p->next)
        if (vis.count(p)) return true;
    return false;
}

方案三：拼接轉環檢測（創新思路）

將 head1 尾節點連接到 head2 頭。若原鏈表相交，新鏈表必有環；否則無環。用快慢指針檢測環。缺點：修改了鏈表結構，需恢復；多線程不安全。

bool intersectCycle(ListNode* h1, ListNode* h2) {
    if (!h1 || !h2) return false;
    // 找 h1 尾節點
    ListNode* tail = h1;
    while (tail->next) tail = tail->next;
    // 拼接
    tail->next = h2;
    // 快慢指針檢測環
    ListNode *slow = h2, *fast = h2;
    bool hasCycle = false;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) { hasCycle = true; break; }
    }
    // 恢復
    tail->next = nullptr;
    return hasCycle;
}

方案四：尾節點比較（最優工程方案）

核心洞察：若兩鏈表相交，從交點開始後續節點完全共享，**尾節點地址必然相同**。反之，尾節點不同則必不相交。

bool intersectTail(ListNode* h1, ListNode* h2) {
    if (!h1 || !h2) return false;
    ListNode *p1 = h1, *p2 = h2;
    while (p1->next) p1 = p1->next;
    while (p2->next) p2 = p2->next;
    return p1 == p2;
}

時間 O(m+n)，空間 O(1)，不修改結構，代碼最簡潔。

進階：求交點節點

若需返回第一個公共節點，可結合長度差對齊：

ListNode* getIntersectionNode(ListNode* h1, ListNode* h2) {
    int len1 = 0, len2 = 0;
    for (auto* p = h1; p; p = p->next) ++len1;
    for (auto* p = h2; p; p = p->next) ++len2;
    ListNode *p1 = h1, *p2 = h2;
    if (len1 > len2) for (int i = 0; i < len1-len2; ++i) p1 = p1->next;
    else for (int i = 0; i < len2-len1; ++i) p2 = p2->next;
    while (p1 && p2) {
        if (p1 == p2) return p1;
        p1 = p1->next; p2 = p2->next;
    }
    return nullptr;
}

總結

• **面試首選**：方案四（尾節點比較），再延伸求交點
• **思維轉化** 關鍵：方案三將「相交」轉化為「有環」，體現問題轉化技巧
• **實際工程** 中鏈表通常帶長度屬性，可直接對齊