LC.相交链表

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

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

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

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

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/jjbj2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法1

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) {
    return null;
  }
  // 设置两个指针
  let p1 = headA;
  let p2 = headB;
  while (p2 !== null) {
    if (!p1 || !p1.next) {
      p1 = headA;
      p2 = p2.next;
    }
    if (p1 === p2) {
      return p1;
    }
    p1 = p1.next;
  }
  return null;
};

解法2

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) {
    return null;
  }
  // 设置两个指针
  let p1 = headA;
  let p2 = headB;
  const set = new Set();
  while (p1 !== null) {
    set.add(p1);
    p1 = p1.next;
  }
  while (p2 !== null) {
    if (set.has(p2)) {
      return p2;
    }
    p2 = p2.next;
  }
  return null;
};