Intersection of Two Linked Lists
两个单向链表共用一个节点池。节点 i 指向节点 next[i]，-1 表示链表结束。链表 A 从节点 headA 开始，链表 B 从节点 headB 开始。节点的存储顺序没有规律，因此请沿着链接查找。
两个链表可能会相交：从某个节点开始，它们会经过相同的节点直到末尾。返回第一个同时属于两个链表的节点的索引；如果它们没有共同节点，则返回 -1。
函数
- nextinteger-array
- 每个节点链接到的节点的索引，或者列表中最后一个节点对应的 -1
- headAinteger
- 列表 A 的第一个节点
- headBinteger
- B 列表的第一个节点
- 返回值integer
- 两个列表共同拥有的第一个节点，如果没有则为 -1
约束条件
2 ≤ n ≤ 104，其中n是next的长度。- 每个
next[i]要么是-1，要么是从0到n-1的节点索引。 0 ≤ headA, headB ≤ n-1，并且headA ≠ headB。- 两个列表都在到达
-1时结束，且不会重复访问任何节点。不存在环。 - 每个节点都在列表 A 中、列表 B 中，或同时在两个列表中。
示例
- 输入
- next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
- 输出
- 1
- 解释
- A 访问
3, 5, 1, 4, 0，B 访问2, 1, 4, 0。从节点1开始，它们访问的每个节点都相同，而 A 更早访问的节点都不在 B 的路径上，所以答案是1。
- 输入
- next = [2, 3, 4, -1, -1]headA = 0headB = 1
- 输出
- -1
- 解释
- 列表 A 是
0, 2, 4，列表 B 是1, 3。它们都以-1结束，且没有经过共同节点，所以答案是-1。
- 输入
- next = [3, 2, 0, -1]headA = 1headB = 0
- 输出
- 0
- 解释
- 列表 A 是
1, 2, 0, 3，列表 B 是0, 3。列表 B 是列表 A 的尾部，因此第一个共享节点就是headB本身，也就是节点0。
进阶
你能否在 O(m + k) 时间内找到该节点，并且只使用 O(1) 额外内存？
提示
逐个打开提示，每个都会多透露一点。
一个节点只有一个
next。两个列表到达同一个节点后，还会再次分开吗？这说明这两个列表的形状是什么样的？如果两个列表长度相同，你可以让它们并排移动，并在两个指针指向同一个节点时停止。问题在于较长列表开头多出的节点。怎样才能让两个指针移动相同的总距离？
让指针
a沿着列表 A 移动，走到末尾时就从headB重新开始。对b也做同样的处理，从headA重新开始。当a == b时停止。该节点就是答案；如果没有这样的节点，答案为-1。
题解
一个节点只有一个 next，所以两个相交的列表之后不会再分开。它们会形成一个 Y，两个各自独立的起点连接到同一个尾部，答案就是交点。两个起点到交点的距离可能不同，所以让两个列表同时前进会错过交点。下面，m 和 k 分别是 A 和 B 的长度。
将 A 的每个节点与 B 的所有节点进行比较
结果正确，但无法在最大的测试中运行完毕
思路
指针是节点索引，向前移动的方式是 node = next[node]。按顺序遍历 A 中的每个节点 a，遍历 B 中的所有节点，并将每个节点与 a 比较。第一个匹配的 a 就是答案，因为 A 中所有更早的节点都已经匹配失败。每遍历 A 中的一个节点，都会重新扫描 B：如果两个列表各有 5000 个节点且没有共享节点，就需要进行 2.5 × 10^7 次比较。
算法
- 将
a = headA。 - 当
a不为-1时，让b从headB遍历到-1。 - 如果某一时刻
b == a，则返回a。 - 否则，将
a移至next[a]并重复。 - 如果列表 A 遍历完了，则返回
-1。
def getIntersectionNode(next, headA, headB):
a = headA
while a != -1:
# Is node a also on list B? Walk all of B to find out.
b = headB
while b != -1:
if a == b:
return a
b = next[b]
a = next[a]
return -1标记列表 B 的节点
思路
对每个节点回答一次“这个节点在 B 上吗？”，遍历 B，并在大小为 n 的布尔数组中标记每个节点。节点索引都是较小的整数，因此用数组就能代替哈希集合。然后从 A 的头节点开始遍历。第一个被标记的节点同时属于两个列表；由于你按顺序遍历 A，它也是第一个这样的节点。在第一个示例中，B 标记了 2, 1, 4, 0，遍历 A 时会先经过 3 和 5，然后在 1 处停下。每个列表只遍历一次，因此时间复杂度为 O(m + k)，代价是需要 n 个标记。
算法
- 创建一个由
n个布尔值组成的数组onB，并将它们都设为 false。 - 从
headB开始遍历列表 B，并为每个节点设置onB[node] = true。 - 从
headA开始遍历列表 A。返回第一个满足onB[node]为 true 的节点。 - 如果列表 A 遍历结束，则返回
-1。
def getIntersectionNode(next, headA, headB):
# Mark every node of list B.
on_b = [False] * len(next)
node = headB
while node != -1:
on_b[node] = True
node = next[node]
# The first marked node on list A is the meeting point.
node = headA
while node != -1:
if on_b[node]:
return node
node = next[node]
return -1切换列表的双指针
思路
在连接处将每个列表拆开：A 中有 x 个私有节点，后面接着 c 个共享节点；B 中有 y 个私有节点，后面接着相同的 c 个共享节点。指针 a 遍历 A，走到 -1 后，再从 headB 重新开始，经过 x + c + 1 + y 次移动后第二次到达连接处。指针 b 遍历 B，然后遍历 A，经过 y + c + 1 + x 次移动后到达连接处。两者移动次数相同。在第一个示例中，x = 2，y = 1，c = 3，两个指针都在移动七次后停在节点 1 上。
如果没有共享尾部，两个指针会在移动 m + 1 + k 次后停在 -1 上（当 m = k 时，移动 m 次后停下），循环会返回 -1。每个指针都会先走到 -1 再切换，这就是它们会在同一位置停下的原因。每个指针最多移动 m + k + 1 次，使用两个索引的内存。
算法
- 将
a = headA设为a，将b = headB设为b。 - 当
a != b时：如果a是-1，就将a移到headB；否则移到next[a]。 - 在同一轮中，如果
b是-1，就将b移到headA；否则移到next[b]。 - 循环结束时，返回
a。它是第一个共享节点，或者是-1。
def getIntersectionNode(next, headA, headB):
a, b = headA, headB
# Each pointer walks its own list, then the other one. Both cover
# the same number of nodes, so they reach the meeting node together,
# or reach -1 together when there is none.
while a != b:
a = headB if a == -1 else next[a]
b = headA if b == -1 else next[b]
return a
易错点和边界情况
- 从最后一个节点直接切换到另一个头节点，跳过
-1处的停止步骤。如果两个链表没有共同节点，两个指针就永远不会指向相同的值，循环会无限运行。 - 让指针从各自的头节点重新开始。这样每个指针都会遍历自己的链表，只有当遍历圈数对齐时它们才会相遇，最多可能需要
(m + 1)·(k + 1)次移动。 - 把数组顺序当作链表顺序。只有当
headA或headB指定时，节点0才是头节点；数组中的相邻元素在链表中并不一定相邻。 - 在 Lua 和 R 中，别忘了数组从 1 开始。节点索引保持从 0 开始，并读取
next[node + 1]。
常见问题3
如何在不使用额外内存的情况下找到两个链表的交点？
运行两个指针。每个指针遍历自己的列表，走到末尾后，从另一个列表的头部继续遍历。它们走过的总距离相同，因此会同时到达第一个共享节点；如果没有共享节点，则会同时到达末尾。
通过比较列表的长度，你能找到交集吗？
是的。统计两个列表的节点数，让较长列表的指针先向前移动两者长度之差，然后让两个指针每次移动一步，直到它们相等。这个方法的时间复杂度也是 O(m + k)，空间复杂度是 O(1)；切换方法无需进行两次计数遍历，也能实现相同的对齐。
查找两个链表的交集的时间复杂度是多少？
双指针法和长度法的运行时间为 O(m + k)，额外内存为 O(1)。将一个列表记在集合或标记数组中，时间复杂度也是线性的，但需要为该列表分配内存。比较每一对节点需要 O(m·k)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def getIntersectionNode(next, headA, headB):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next = [-1, 4, 1, 5, 0, 1] headA = 3 headB = 2
预期输出
1