160.相交链表.md

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：暴力法

思路

对于链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。

复杂度

时间复杂度：O(M * N)O(M∗N), M, N 分别为两个链表的长度。 空间复杂度：O(1)O(1)。

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null
  let pA = headA
  while (pA) {
    let pB = headB
    while (pB) {
      if (pA === pB) return pA
      pB = pB.next
    }
    pA = pA.next
  }
}

方法 2：哈希表

思路

先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。 再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。

复杂度

时间复杂度：O(M + N), M, N 分别为两个链表的长度。 空间复杂度：O(N)，N 为链表 A 的长度。

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null
  const hashmap = new Map()
  let pA = headA
  while (pA) {
    hashmap.set(pA, 1)
    pA = pA.next
  }
  let pB = headB
  while (pB) {
    if (hashmap.has(pB)) return pB
    pB = pB.next
  }
}

方法 3：双指针

如果链表没有交点

两个链表长度一样，第一次遍历结束后 pA 和 pB 都是 null，结束遍历 两个链表长度不一样，两次遍历结束后 pA 和 pB 都是 null，结束遍历

复杂度

时间复杂度：O(M + N) , M, N 分别为两个链表的长度。 空间复杂度：O(1)。

/**
 * 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 || !headB) return null

  let pA = headA,
    pB = headB
  while (pA !== pB) {
    pA = pA === null ? headB : pA.next
    pB = pB === null ? headA : pB.next
  }
  return pA
}