相交链表

Tips

题目类型: LinkedList, HashMap

题目

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

示例

输入:

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

输出: c1

题解

JavaScript

基本的原理就是当一条链表走到头了, 就把它换成另一条从头开始. 这样的目的是保证在两条链表置换后, 指针可以齐头并进, 比如示例中, 当两条链条都变化后, 一个指针就会在 a1, 另一个指针在 b2 上, 那这两个指针齐头并进. 就能找到交点.

/**
 * 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)