160. 相交链表

这是经典的「相交链表」问题（LeetCode 160）。我们可以用 双指针法 高效解决，时间复杂度 O(m+n)，空间复杂度 O(1)。

✅ 解题思路：双指针

核心思想：

• 指针 pA 从 headA 开始，走到尾后跳到 headB
• 指针 pB 从 headB 开始，走到尾后跳到 headA
• 如果有交点，两者会在交点相遇；否则都走到 null

为什么能相遇？ 假设链表 A 独有部分长度 a，B 独有部分长度 b，公共部分长度 c。 pA 走过的路径：a + c + b pB 走过的路径：b + c + a 两者总路程相同，必然在交点（或 null）相遇。

Java 代码实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null headB == null) {
        return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            // pA 走完自己的链表后跳到 headB
            pA = (pA == null) ? headB : pA.next;
            // pB 走完自己的链表后跳到 headA
            pB = (pB == null) ? headA : pB.next;
        }

        // 如果相交，返回交点；否则返回 null
        return pA;
    }
}

关键点说明

1. 边界处理：任一链表为空直接返回 null
2. 循环终止条件：pA == pB 时退出（可能是交点，也可能是都为 null）
3. 指针重定向时机：当前指针为 null 时才切换到另一链表头（不是走到最后一个节点就切换！）

⏱️ 复杂度分析

• 时间复杂度：O(m + n)：（每个指针最多遍历两个链表）
• 空间复杂度：O(1)：（仅使用两个指针）

❌ 其他方法对比

这个解法巧妙利用了路径对齐的思想，是面试高频考点，建议熟练掌握！