相交链表

Tips

题目类型: LinkedList, HashMap

题目

给你两个单链表的头节点 headA 和 headB, 请你找出并返回两个单链表相交的起始节点. 如果两个链表没有交点, 返回 null. 题目数据保证整个链式结构中不存在环. 注意, 函数返回结果后, 链表必须保持其原始结构.

示例

输入:

     a1 → a2 ↘
              c1 → c2 → c3
b1 → b2 → b3 ↗

输出: c1

题解

JavaScript

假设链表 A 的长度为 a, 链表 B 的长度为 b, 相交部分(如果有的话)的长度为 c.

• A 走过的路径长度为 a + (b - c) 或 a (如果不相交)
• B 走过的路径长度为 b + (a - c) 或 b (如果不相交)

可以看到, 如果两个链表相交, 那么 A 和 B 一定会在相交节点相遇, 因为它们走过的总长度相同 a + b - c. 如果不相交, 它们最终都会变成 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) {
  let p = headA,
    q = headB

  while (p !== q) {
    p = p === null ? headB : p.next
    q = q === null ? headA : q.next
  }

  return p
}

JavaScript - HashMap

想必大家都能想到这个方法, 用 HashMap 嘛. 先遍历第一个链表, 将节点依次存到 HashMap 中, 再遍历第二个链表, 如果能在 HashMap 中找到引用, 就说明找到了相交节点呗; 如果第二个链表遍历到头了, 还没在 HashMap 中找到引用, 说明就不相交.

var getIntersectionNode = function (headA, headB) {
  let p = headA
  let q = headB
  const set = new Set()

  while (p) {
    set.add(p)
    p = p.next
  }

  while (q) {
    if (set.has(q)) {
      return q
    }

    q = q.next
  }

  return null
}

时间复杂度: O(m + n)

空间复杂度: O(n)