复盘 · LC 160 相交链表（二刷）

题目

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

题意

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

• 两条链长度可以不同；不相交是合法情况。
• 进阶：O(1) 额外空间。

边界：一条为空、在头部相交、在尾部相交、完全不相交。

涉及算法

标签	一句话
哈希表 / Set	先把 A 的节点全放进集合，再扫 B
双指针交叉走	走完自己的链后接到对面，路程对齐后在交点（或同为 null）相遇

教程对照：13 · 链表进阶。

评价我的解法

相对 7/20 首刷 的 Set，今天直接写出 O(1) 空间双指针——二刷满分升级。

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

var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) {
    return null;
  }
  let nodeA = headA;
  let nodeB = headB;
  while (nodeA != nodeB) {
    nodeA = nodeA ? nodeA.next : headB;
    nodeB = nodeB ? nodeB.next : headA;
  }
  return nodeA;
};

判断正确，本地还构造了 Y 形相交链验证。

• 时间 O(m + n)，空间 O(1)。
• 优点：与最佳题解同构；空链提前返回；!= / !== 在节点引用上效果一致。
• 可打磨：面试口述时把「a+c+b = b+c+a」讲清楚；不相交时两人最终都走完对面后同为 null 退出。

小结：今天四题里这题质量最高——模板已稳。

最佳题解

与你今天写法等价（仅命名）：

/**
 * @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;
};

• 时间 O(m + n)，空间 O(1)。
• 直觉：独有段 a、b，公共段 c；交叉走后总路程对齐，必在交点或 null 相遇。

关联题目

题	为何相关
141. 环形链表	相遇问题同一家族
142. 环形链表 II	找入口，路程对齐升级
21. 合并两个有序链表	双指针扫两条链

一句话带走

相交链表二刷 = 走完接对面，路程对齐；Set 能讲，双指针才是 O(1) 答卷。