🔗 相交链表

题目来源：160. 相交链表 – 力扣（LeetCode）

---

📌 题目描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

图示两个链表在节点 c1 开始相交：

• 相交定义：两个链表在某个节点 c 处“合并”，即从该节点开始，后续所有节点完全共享（内存地址相同）。
• 保证：链表中不存在环。
• 要求：函数返回后，链表必须保持原始结构（不能修改指针结构）。

---

✅ 示例解析

示例 1：

• 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
• 输出：Intersected at '8'
• 解释：
  • 链表 A：4 → 1 → 8 → 4 → 5
  • 链表 B：5 → 6 → 1 → 8 → 4 → 5
  • 从值为 8 的节点开始，两个链表共享后续所有节点。

示例 2：

• 输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• 输出：Intersected at '2'
• 解释：在值为 2 的节点处相交。

示例 3：

• 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
• 输出：No intersection（返回 null）
• 解释：两个链表无交点。

---

⚠️ 提示

• listA 中节点数目为 m，listB 中节点数目为 n
• 1 <= m, n <= 3 * 10⁴
• 1 <= Node.val <= 10⁵
• 0 <= skipA <= m
• 0 <= skipB <= n
• 若相交，则 intersectVal == listA[skipA] == listB[skipB]

---

💡 解法：双指针“浪漫相遇”法 —— O(m + n) 时间，O(1) 空间

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        
        while (pA != pB) {
            pA = (pA != null) ? pA.next : headB;
            pB = (pB != null) ? pB.next : headA;
        }
        
        return pA;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(m + n)
  • 最坏情况下，每个指针都遍历完自己的链表后，再遍历对方的链表，总共走 m + n 步。
  • 实际上，当两个链表有交点时，会在 m + n 步内相遇。
• 空间复杂度：O(1) ✅
  • 仅使用两个指针 pA 和 pB，无额外数据结构。

---

🧩 解题思路

1. 核心思想：双指针走完自己的路，再走对方的路，最终相遇
   • 设链表 A 长度为 a + c（a 是独有部分，c 是公共部分）
   • 设链表 B 长度为 b + c（b 是独有部分，c 是公共部分）
   • 如果两个指针分别从 headA 和 headB 出发，并在到达末尾时跳转到对方的头节点：
     • pA 走的路径：A → null → B，总长 a + c + b
     • pB 走的路径：B → null → A，总长 b + c + a
   • 当 pA 和 pB 都走了 a + b + c 步时，它们会同时到达相交点。
2. 为什么能相遇？
   • 如果有交点：
     • pA 走完 A 后跳到 B，pB 走完 B 后跳到 A。
     • 当 pA 走了 a + c + b 步时，它正好在公共部分的起点。
     • 同理，pB 也走了 b + c + a 步，到达同一位置。
     • 由于 a + c + b = b + c + a，它们会同时到达交点。
   • 如果无交点：
     • 两个指针最终都会走完 m + n 步，同时变为 null，此时 pA == pB == null，跳出循环，返回 null。
3. 代码逻辑详解：java深色版本while (pA != pB) { pA = (pA != null) ? pA.next : headB; pB = (pB != null) ? pB.next : headA; }
   • 循环条件：pA != pB，直到它们相遇（指向同一节点或都为 null）
   • 指针移动规则：
     • 如果 pA 还没到尾部，就继续前进 pA.next
     • 如果 pA 到了尾部（null），就跳到 headB 开始遍历 B
     • 同理处理 pB
   • 最终 pA 和 pB 会在交点或 null 处相遇。
4. 举例说明：
   对 A: 4→1→8→4→5, B: 5→6→1→8→4→5，交点为 8：
   • pA 路径：4→1→8→4→5→5→6→1→8
   • pB 路径：5→6→1→8→4→5→4→1→8
   • 当 pA 和 pB 都走到第 9 个节点时，都在 8 处相遇 ✅
5. 边界处理：
   • 任一链表为空：pA 或 pB 一开始就为 null，最终都会走到 null，返回 null。
   • 无交点：两个指针最终都为 null，循环结束，返回 null。
   • 有交点：必在交点处相遇。