Day13-相交链表

🔗 LeetCode 160 - Intersection of Two Linked Lists

📌 题目描述

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

示例：

A:       a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

输出：c1

---

💡 解题思路

我们可以使用“双指针法”：

• 分别从两个链表的头开始遍历
• 当指针 A 到尾部时，转到 B 链表头；指针 B 到尾部时，转到 A 链表头
• 如果有交点，最终两个指针会在交点相遇
• 否则，都会变为 null，表示没有相交

核心思想：两个指针走过的路程一样，最终会在交点重合或同时为 null

---

✅ JavaScript 实现

var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB) return null;

    let pA = headA, pB = headB;

    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA : pB.next;
    }

    return pA;
};

---

🧠 思考拓展

• 如果不允许修改原链表结构，还能怎么做？
• 空间复杂度可以为 O(1) 吗？
• 如果链表有环，还能找到相交节点吗？（结合 LeetCode 142）