两个链表的第一个公共结点

题目描述

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

思路

首先，获取到两个链表的长度L1和L2；

然后，让长链表先走L1-L2步，使得两个链表在同一起点上；

接着，两个链表同时前进，并且比较每个结点值；

最后，当判断第一个相等的结点时，将该节点返回；

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2) {
  let l1 = getLength(pHead1);
  let l2 = getLength(pHead2);
  let lang, short, k;
  if (l1 <= l2) {
    short = pHead1;
    lang = pHead2;
    k = l2 - l1;
  } else {
    short = pHead2;
    lang = pHead1;
    k = l1 - l2;
  }
  // 让长链表先走K步
  while (k--) {
    lang = lang.next;
  }
  while (lang && short) {
    if (lang === short) {
      return lang;
    }
    lang = lang.next;
    short = short.next;
  }
  return null;
}

function getLength(head) {
  let num = 0;
  while (head) {
    num++;
    head = head.next;
  }
  return num;
}