160. Intersection of Two Linked Lists

求两个链表的交点。

• 时间复杂度：O(M + N)， 空间复杂度：O(N)
• Runtime: 92 ms, faster than 78.42%
• Memory Usage: 45.4 MB, less than 80.78%

思路：链表相等的情况下一直next，next到null的时候，换到另一个链表的开头，再次相等的时候，就是交点。

/**
 * 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 === null || headB === null) return null;
  let pA = headA;
  let pB = headB;
  while (pA !== pB) {
    pA = (pA !== null) ? pA.next : headB;
    pB = (pB !== null) ? pB.next : headA;
  }
  return pA;
};

使用额外的空间实现

• 时间复杂度O(m+n)，空间复杂度O(m)
• Runtime: 100 ms, faster than 53.69%
• Memory Usage: 47 MB, less than 11.78%

var getIntersectionNode = function(headA, headB) {
  let visited = new Set();
  let p = headA;
  while (p) {
    visited.add(p);
    p = p.next;
  }
  p = headB;
  while (p) {
    if (visited.has(p)) {
      return p;
    }
    p = p.next;
  }
  return p;
};