[160] 相交链表 (Intersection of Two Linked Lists)

标签：链表 双指针 数学
难度：🟢 Easy

🧠 核心思维：路径拼接 (A+B = B+A)

TIP

一句话逻辑： "我走过你走的路，你也走过我走的路，我们终将在终点（或相交点）相遇。"

• 痛点：两个链表长度不一样 ()，无法像拉链一样对齐比较。
• 策略：
  1. 指针 A 走完 List A 后，自动跳到 List B 的头继续走。
  2. 指针 B 走完 List B 后，自动跳到 List A 的头继续走。
• 效果：两者的总路程都变成了 。路程相等，速度相等，必在终点（交点）相遇。

---

💻 标准代码 (C++)

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pA = headA;
    ListNode *pB = headB;
    
    // 只要没相遇（包括同时指向 nullptr 的情况），就继续走
    while (pA != pB) {
        // > [!IMPORTANT] 极简三元运算符
        // 如果走到尽头(nullptr)，就转场到另一条链表；否则继续前行
        pA = (pA == nullptr) ? headB : pA->next;
        pB = (pB == nullptr) ? headA : pB->next;
    }
    
    return pA; // 返回相遇点（也就是交点，或者 null）
}

📊 复杂度对比

方法	时间复杂度	空间复杂度	评价
哈希表法		或	逻辑简单，但内存占用大
双指针法			最优解，无需额外空间

双指针法 (A+B) 处理不相交链表

问：如果两个链表根本不相交，双指针法会不会死循环？

答：不会。它们会在 nullptr 处相遇。

• 原理：如果不相交，指针 pA 和 pB 会分别走完 Len(A) + Len(B) 的路程。
• 退出时刻：
  • pA 走完 A 转走 B，最后走到 B 的尾部 nullptr。
  • pB 走完 B 转走 A，最后走到 A 的尾部 nullptr。
  • 此时 pA == pB (都等于 nullptr)，while 循环条件终止，函数返回 null。