题目

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

方法

参考：https://www.cnblogs.com/edisonchou/p/4822675.html
时间复杂度：O(m + n)

思路

题目表述，找出第一个公共结点。按照题意，两个链表应该是呈，平方的Y状，而不会是X状。如下图

简单的办法，直接暴力。但是复杂度较高。
观察上图，既然两个链表在第一个公共节点后，完全重叠。那么重叠的节点个数应该是相同的，所以可以通过从链表的尾部，两个链表同时向前比对，如果碰到不同的节点，那么上一个节点就是最后一个公共节点。那么就找到了题目要求的第一个公共节点

具体办法

链表无法逆序遍历，所以需要先顺序遍历链表将链表节点存储。为了方便两个链表从尾开始比较，这里使用栈，将2个链表顺序遍历入栈。然后从栈顶开始比较，相同则出栈，一直到栈顶不同，则前一个出栈元素就是题目的第一个公共节点

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2) {
  // write code here
  let s1 = []
  let s2 = []
  let p1 = pHead1
  let p2 = pHead2
  while (p1) {
    s1.push(p1)
    p1 = p1.next
  }
  while (p2) {
    s2.push(p2)
    p2 = p2.next
  }
  let result
  while (s1.length > 0 && s2.length > 0) {
    let i1 = s1.pop()
    let i2 = s2.pop()
    if (i1.val === i2.val) {
      result = i1
    } else {
      break
    }
  }
  return result
}