怎样找两个链表的相交节点？为什么双指针换头一定会相遇？

简答

两个单链表从某个节点开始共用后面的部分，就像两条小路汇进同一条大路，汇合的那个节点就是相交节点。题目要返回它，不相交就返回 null，而且不能改动链表的结构。

最好记的做法是双指针换头。指针 a 从 A 的头出发，b 从 B 的头出发，每次各走一步；a 走到尾就跳到 B 的头，b 走到尾就跳到 A 的头。两个指针第一次相等时，指向的就是相交节点。

它一定会相遇，是因为两个指针走的路程被拉平了。设 A 独有部分长 x，B 独有部分长 y，公共部分长 z。a 走完 x + z 再走 y 到达交点，b 走完 y + z 再走 x 也到达交点，两者都走了 x + y + z 步。不相交时 z 是 0，两个指针都走 m + n 步后同时变成 null，循环也会结束。

这个做法时间 O(m + n)，额外空间 O(1)，正好满足题目的进阶要求。要注意，判断相交比的是节点引用，不是节点的值，值相同的两个节点不一定是同一个节点。

先看代码

getIntersectionNode 只有一个循环，关键是走到 null 后换到另一个链表的头。build 用来把数组建成链表，第二个参数是接在后面的公共部分。

function build(values, tail = null) {
  let head = tail;
  for (let i = values.length - 1; i >= 0; i -= 1) {
    head = { value: values[i], next: head };
  }
  return head;
}

function getIntersectionNode(headA, headB) {
  let a = headA;
  let b = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

const common = build([8, 4, 5]);
const listA = build([4, 1], common);
const listB = build([5, 6, 1], common);
console.log(getIntersectionNode(listA, listB).value); // 8

const shared = build([2, 4]);
console.log(getIntersectionNode(build([1, 9, 1], shared), build([3], shared)).value); // 2

console.log(String(getIntersectionNode(build([2, 6, 4]), build([1, 5])))); // null

前两组对应 LeetCode 的示例 1 和示例 2，第三组是示例 3 的不相交情况。示例 1 里 A 和 B 都有值为 1 的节点，但它们是两个不同的对象，所以交点不是 1，而是值为 8 的那个共用节点。题目也特别说明了这一点，所以循环条件用的是 a !== b，比较引用。

为什么换头以后一定会相遇

两个链表长度不同，同时出发的指针不会同时到达交点。换头的作用就是让两个指针补上对方多出来的那段路。

用示例 1 算一下。A 独有部分 4 → 1 长 2，B 独有部分 5 → 6 → 1 长 3，公共部分 8 → 4 → 5 长 3。指针 a 先走完 A 的 5 个节点，跳到 B 的头，再走 3 步到达 8，一共走了 2 + 3 + 3 = 8 步。指针 b 走完 B 的 6 个节点，跳到 A 的头，再走 2 步到达 8，一共是 3 + 3 + 2 = 8 步。步数相同，所以它们在 8 这里同时到达。

不相交时公共部分长度是 0。示例 3 里 A 长 3、B 长 2，两个指针都走 5 步后同时停在 null，null === null 成立，循环结束并返回 null。所以不需要额外判断不相交的情况，也不会死循环。

要注意代码里是“走到 null 再换头”，不是“走到最后一个节点就换头”。null 被当作一步，正是它保证了不相交时两个指针能同时到达 null。如果跳过 null 直接换头，不相交时两个指针永远不会相等。

其他做法

用 Set 也能做：先把 A 的所有节点放进 Set，再遍历 B，第一个出现在 Set 里的节点就是交点。思路直接，但要 O(m) 的额外空间。

还可以先求两个链表的长度，让长的那个先走长度差那么多步，再一起走，第一次相等就是交点。它也是 O(1) 空间，本质上和换头一样，都是把两个指针对齐到离交点相同距离的位置。

同样用双指针处理链表的题，还有找环的入口，见《环形链表怎样找到入环点？为什么相遇后从头再走就能找到？》。

常见追问

如果链表里有环，这个方法还能用吗？

题目保证整个链表结构里没有环，所以不用考虑。如果有环，指针可能一直在环里绕，换头的步数计算也不再成立，要先用快慢指针判环再分情况处理。

为什么不能修改链表来做标记？

题目要求函数返回后链表保持原来的结构。比如把走过的节点的 next 改掉做标记，虽然能找到交点，但破坏了输入，也会影响共用这两个链表的其他代码。

两个链表在交点之后还会分开吗？

不会。单链表每个节点只有一个 next，两个链表从交点开始，后面的节点都是同一批，所以相交的形状一定是 Y 形，不会是 X 形。