剑指offer（36）两个链表中的第一个公共节点

题目描述

输入两个链表，找出它们的第一个公共结点。

题目分析

我发现关于链表的题都涉及双指针，大家做的时候记得用双指针。

题目理解了就很好做了，比较简单，先在长的链表上跑，直到长的和短的一样长，再一起跑，判断节点相等的时候就可以了。

代码

function FindFirstCommonNode(pHead1, pHead2) {

  const len1 = getLinkLength(pHead1),

    len2 = getLinkLength(pHead2);

  let pLong = pHead1,

    pShort = pHead2,

    lenGap = len1 - len2;

  if (len1 < len2) {

    pLong = pHead2;

    pShort = pHead1;

    lenGap = len2 - len1;

  }

  while (lenGap--) {

    pLong = pLong.next;

  }

  while (pLong !== null) {

    // pLong,pShort一起跑

    if (pLong.val === pShort.val) {

      return pLong;

    }

    pLong = pLong.next;

    pShort = pShort.next;

  }

  return null;

}

function getLinkLength(pHead) {

  let length = 0;

  while (pHead !== null) {

    pHead = pHead.next;

    length++;

  }

  return length;

}