相交链表

160. 相交链表

来源：力扣（LeetCode） 链接 (opens new window)：https://leetcode.cn/problems/intersection-of-two-linked-lists/ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

github (opens new window)

问题

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

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路

var getIntersectionNode = function (headA, headB) {
  let set = new Set();

  let p1 = headA;
  let p2 = headB;
  while (p1 !== null) {
    set.add(p1);
    p1 = p1.next;
  }

  while (p2 !== null) {
    if (set.has(p2)) {
      return p2;
    }
    p2 = p2.next;
  }

  return null;
};