160.相交链表

题目

LeetCode 简单

题目

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

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

---

题解

方法：Set

Set O(m+n) O(m)

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null,
): ListNode | null {
  let tempSet = new Set()
  let p1 = headA
  while (p1) {
    tempSet.add(p1)
    p1 = p1.next
  }

  let p2 = headB
  while (p2) {
    if (tempSet.has(p2)) {
      return p2
    }
    p2 = p2.next
  }
  return null
}

方法：双指针

双指针 O(m+n) O(1)

function getIntersectionNode2(
  headA: ListNode | null,
  headB: ListNode | null,
): ListNode | null {
  if (headA === null || headB === null) {
    return null
  }
  let pA = headA,
    pB = headB
  while (pA !== pB) {
    pA = pA === null ? headB : pA.next
    pB = pB === null ? headA : pB.next
  }
  return pA
}