LeetCode第160题:相交链表

题干

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

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

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
复制代码

解法：双指针

这道题需要注意的是我们不能只比较链表中元素中的值，因为这里的相交是指两个链表公用一块内存空间，所以我们比较的应该是内存地址。

每步操作需要同时更新指针pA 和pB；

如果指针pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。

如果指针 pA 为空，则将指针pA 移到链表headB 的头节点；如果指针 pB 为空，则将指针pB 移到链表 headA 的头节点。

当指针 pA 和pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

执行用时：104 ms, 在所有 JavaScript 提交中击败了79.13%的用户

内存消耗：44.7 MB, 在所有 JavaScript 提交中击败了33.04%的用户

var getIntersectionNode = function (headA, headB) {
    if (headB == null || headA == null) {
        return null
    }
    let p1 = headA;
    let p2 = headB;
    while (p1 != p2) {
        p1=p1==null?headB:p1.next
        p2=p2==null?headA:p2.next
    }
    return p1
};
复制代码