复盘 · LC 160 相交链表

代码目录曾误标为 106（106 是中序后序建树）；题目正确题号为 160。

题目

• 题号：LeetCode 160
• 名称：相交链表（Intersection of Two Linked Lists）
• 难度：Easy
• 链接：leetcode.cn/problems/intersection-of-two-linked-lists
• 今日代码：160-相交链表/index.js

题意

给定两条单链表头结点 headA、headB，若它们在某节点起开始共用同一段后缀（节点引用相同，不只是值相同），返回相交的那个节点；否则返回 null。

• 相交指的是同一个节点对象，不是 val 碰巧相等。
• 两条链长度可以不同；不相交是合法情况。
• 题目通常要求尽量 O(1) 额外空间（进阶）。

边界：一条为空、在头部相交、在尾部相交、完全不相交成「Y」或两条平行。

涉及算法

标签	一句话
哈希表 / Set	先把 A 的节点全放进集合，再扫 B 看是否出现过
双指针	两指针分别走完自己的链后接到另一条，路程对齐后会在交点相遇

教程对照：13 · 链表进阶（环检测、相交、合并）。

评价我的解法

我的代码（摘自 160-相交链表/index.js，不含本地测例）：

var getIntersectionNode = function (headA, headB) {
  const set = new Set();
  let nodeA = headA;
  while (nodeA) {
    set.add(nodeA);
    nodeA = nodeA.next;
  }
  let nodeB = headB;
  while (nodeB) {
    if (set.has(nodeB)) {
      return nodeB;
    }
    nodeB = nodeB.next;
  }
  return null;
};

判断正确，面试也能讲清：「用节点引用当 key，值相等不算相交」。

• 时间 O(m + n)，空间 O(m)（A 的长度）。
• 优点：直观、不易写错、空链自然返回 null。
• 可改进：进阶要求 O(1) 空间时，Set 不够「满分」；需要双指针交叉走。

本地测试只跑了 getIntersectionNode(null, null)，功能上对，但没构造相交用例，复盘时建议自己搭两条链验证一次。

最佳题解

双指针交叉走（O(1) 空间）：

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) return null;
  let pA = headA;
  let pB = headB;
  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }
  return pA; // 相交点，或同时为 null（不相交）
};

• 时间 O(m + n)，空间 O(1)。
• 直觉：设 A 独有段长 a、B 独有段长 b、公共段长 c。
  pA 走完 A 再走 B：路程 a+c+b；pB 走完 B 再走 A：路程 b+c+a。
  总长相同，之后同步，要么在交点相遇，要么都走到 null。

面试可先讲 Set，再主动升级到双指针，展示空间优化意识。

关联题目

题	为何相关
141. 环形链表	快慢指针；链表「相遇」同一家族
142. 环形链表 II	找环入口，和「对齐路程」思路相通
21. 合并两个有序链表	双指针在链表上的另一高频用法

一句话带走

相交链表：Set 保正确；双指针交叉走拿 O(1) 空间——讲清「走完接对面，路程对齐」。