160. 相交链表
题目描述
给出两条单链表的头节点 headA 和 headB。两条链表可能从某个节点开始共用后面的全部节点，这个节点就是相交起点。返回相交起点；若两条链表没有公共节点，返回 null。
相交指的是同一个节点对象，而不是节点值相等。整个结构中没有环。函数结束后，两条链表必须保持原来的结构。
评测时会给出 intersectVal（相交起点的值，不相交时为 0）、数组形式的 listA 与 listB，以及 skipA、skipB（分别表示从各自头节点走多少个节点到达相交起点）。系统据此建好链表，只把 headA 和 headB 交给你的函数。返回值正确即判为通过。页面上的输出显示相交起点的值，不相交时显示 null。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：8
解释：A 中前 2 个节点、B 中前 3 个节点之后，两条链表汇合到值为 8 的同一个节点。两边值为 1 的节点是不同的对象，不算相交。
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：2
解释：A 跳过 3 个节点、B 跳过 1 个节点后，汇合到值为 2 的节点。
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null
解释：两条链表没有公共节点，返回 null。
数据范围
listA有m个节点，listB有n个节点。1 <= m, n <= 3 * 10^41 <= Node.val <= 10^50 <= skipA <= m0 <= skipB <= n- 两条链表不相交时，
intersectVal为 0。 - 两条链表相交时，
intersectVal == listA[skipA] == listB[skipB]。
进阶：能否做到 O(m + n) 时间、只用 O(1) 额外空间？
解题思路：双指针（交换起点）
双指针分别走 A、B；走到末尾后切换到另一条链表。两者总行程都是 len(A)+len(B)，会在相交点或 None 汇合。
为什么正确
切换后，两个指针还未走过的路径长度相同，因此相遇位置必然一致。
复杂度分析
时间 O(m+n)，空间 O(1)。
易错点
比较节点对象身份而非节点值；不同节点可能有相同值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getIntersectionNode(self, headA,headB):
a,b=headA,headB
while a is not b:
a=headB if a is None else a.next
b=headA if b is None else b.next
return aclass Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a = headA, *b = headB;
while (a != b) {
a = a == nullptr ? headB : a->next;
b = b == nullptr ? headA : b->next;
}
return a;
}
};func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
if a == nil {
a = headB
} else {
a = a.Next
}
if b == nil {
b = headA
} else {
b = b.Next
}
}
return a
}var getIntersectionNode = function(headA, headB) {
let a = headA, b = headB;
while (a !== b) {
a = a === null ? headB : a.next;
b = b === null ? headA : b.next;
}
return a;
};function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
let a = headA, b = headB;
while (a !== b) {
a = a === null ? headB : a.next;
b = b === null ? headA : b.next;
}
return a;
};其他解法
两种方法时间都是 O(m+n)；哈希集合用额外空间换取直观，双指针利用两条路径总长相等做到 O(1) 空间。
解法 2：哈希集合 时间 O(m+n)，空间 O(m)
先遍历链表 A，把每个节点的引用放进哈希集合。再遍历链表 B，第一个出现在集合中的节点就是相交起点。B 走完都没有命中，返回空。
思路直接，容易想到。需要 O(m) 额外空间，不满足进阶要求的 O(1) 空间。
class Solution:
def getIntersectionNode(self, headA, headB):
seen = set()
a = headA
while a:
seen.add(a)
a = a.next
b = headB
while b:
if b in seen:
return b
b = b.next
return Noneclass Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> seen = new HashSet<>();
for (ListNode a = headA; a != null; a = a.next) seen.add(a);
for (ListNode b = headB; b != null; b = b.next) {
if (seen.contains(b)) return b;
}
return null;
}
}class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*> seen;
for (ListNode *a = headA; a != nullptr; a = a->next) seen.insert(a);
for (ListNode *b = headB; b != nullptr; b = b->next) {
if (seen.count(b)) return b;
}
return nullptr;
}
};func getIntersectionNode(headA, headB *ListNode) *ListNode {
seen := map[*ListNode]bool{}
for a := headA; a != nil; a = a.Next {
seen[a] = true
}
for b := headB; b != nil; b = b.Next {
if seen[b] {
return b
}
}
return nil
}var getIntersectionNode = function(headA, headB) {
const seen = new Set();
for (let a = headA; a !== null; a = a.next) seen.add(a);
for (let b = headB; b !== null; b = b.next) {
if (seen.has(b)) return b;
}
return null;
};function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
const seen = new Set<ListNode>();
for (let a = headA; a !== null; a = a.next) seen.add(a);
for (let b = headB; b !== null; b = b.next) {
if (seen.has(b)) return b;
}
return null;
};