相交链表 easy 哈希表双指针

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

example1:

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。

题目分析

首先存在两个链表，然后题目默认给出的是相交链表，所以我们需要遍历两条链表，然后找到相交节点。

最简单的方法就是利用哈希表对遍历过的元素进行存储，如果遍历到相同的元素，那么就说明两个链表相交了，而且相交的节点就是我们需要的节点。

其次可以通过双指针的方法，同时遍历对应的链表，如果到尾部就换另外一个链表，然后继续遍历（每个链表都遍历两次，指针到同一个位置就是相交点）。

解题方法

1. 哈希表

遍历headA时利用Set存储存储headA上的每一个节点，然后遍历 headB 时判断该节点是否存在，如果存在说明这个就是交点，否则返回null即可。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  const map = new Map<ListNode, number>()
  let p = headA
  while (p) {
    map.set(p, 1)
    p = p.next
  }
  let q = headB
  while (q) {
    if (map.get(q)) {
      return q
    }
  }
  return null
}

2. 双指针

同时遍历对应的链表，如果到尾部就换另外一个链表，然后继续遍历（每个链表都遍历两次，指针到同一个位置就是相交点）。

假设 headA 为 1 -> 2 ——> 3 -> 4, 而 headB 为 6 -> 3 -> 5，当第一次遍历完时 p（从 headA 开始） 会走到 4，q（从 headB 开始） 会走到 5，此时 p 继续以 headB 开始遍历，而 q 从 headA 开始遍历，两个同时走 3 步时会在 3 节点相遇，即是相交点。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let p = headA,
    q = headB
  while (p !== q) {
    p = p ? p.next : headB
    q = q ? q.next : headA
  }
  return p
}