题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

测试用例

用例1 ：

• 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
• 输出：Reference of the node with value = 8
• 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为[4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

用例2

• 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
• 输出：Reference of the node with value = 2
• 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

思路

两个指针，同时遍历两个链表，如果还没有找到相同的结点，同时一个链表遍历完了，那就让该指针去遍历另一个链表，相当于遍历的长度是两个链表的总长度，遍历完总长度之后，如果还没有找到，那就证明没有公共结点，返回null

代码实现

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  let curA = headA;
  let curB = headB;

  let lenA = 0;
  let lenB = 0;
  if (!curB || !curA) {
    return null;
  }
  while (curA) {
    lenA++;
    curA = curA.next;
  }

  while (curB) {
    lenB++;
    curB = curB.next;
  }
  // x x x
  // x x
  curA = headA;
  curB = headB;
  let len = lenA + lenB;
  while (len) {
    if (curA === curB) {
      return curA;
    }
    curA = curA.next;
    curB = curB.next;
    if (!curA) {
      curA = headB;
    }
    if (!curB) {
      curB = headA;
    }
    len--;
  }
  return null;
};