链表的相交问题：判断两个链表是否相交、找到第一个相交节点
链表相交这个问题，说实话，我第一次遇到是在一次技术面里。当时面试官问：「两个单链表，怎么判断它们有没有相交？」我第一反应是「这还不简单，遍历呗」。结果真上手写代码的时候，才发现坑不少。今天咱们就把这个知识点彻底讲透。
什么是链表相交？
两个链表相交，不是指它们有相同的值，而是指它们共享了同一个内存节点。说白了，就是两个链表从某个节点开始，后面的节点都是同一个。
你想想看，单链表每个节点只有一个 next 指针。如果两个链表相交了，那从相交点往后，它们就变成了一条路。就像两条河汇成一条河一样。
关键点：相交 ≠ 值相等。两个节点值相同但地址不同，不算相交。只有地址相同才算。
相交的几种形态
我总结了一下，链表相交常见的有三种情况：
- Y 型相交：两个链表从某个节点开始合并，之后完全重合。这是最常见的形态。
- V 型相交：两个链表在某个节点相遇，然后各自继续。但单链表做不到，因为一个节点只有一个 next。
- 无相交：两个链表各走各的，谁也不挨着谁。
嗯，这里要注意：单链表不可能出现 X 型相交，因为一个节点只有一个 next 指针。如果相交了，后面的路径一定是唯一的。
判断两个链表是否相交
判断相交，最直接的办法就是看最后一个节点是否相同。为什么？因为如果两个链表相交了，它们最后一个节点一定是同一个。
我在项目中遇到过这样一个场景：系统里有两个日志链表，需要判断它们是否共享了某段历史记录。我当时就是用这个办法，先找到两个链表的尾节点，比较地址就行了。
方法一：尾节点比较法
// 判断两个链表是否相交
int isIntersect(ListNode* headA, ListNode* headB) {
if (headA == NULL || headB == NULL) return 0;
ListNode* pA = headA;
ListNode* pB = headB;
// 找到链表A的尾节点
while (pA->next != NULL) {
pA = pA->next;
}
// 找到链表B的尾节点
while (pB->next != NULL) {
pB = pB->next;
}
// 比较尾节点地址
return (pA == pB) ? 1 : 0;
}这个方法的时间复杂度是 O(m+n)，空间复杂度是 O(1)。说白了，就是跑两趟，记下尾巴，比一比。
找到第一个相交节点
判断相交只是第一步，很多时候我们需要找到第一个相交的节点。比如调试内存泄漏时，要知道两个链表是从哪里开始共享的。
我个人习惯用「双指针法」来解决这个问题。思路其实很简单：
- 先算出两个链表的长度
- 让长链表的指针先走差值步
- 然后两个指针一起走，第一次相遇就是相交点
为什么会这样？因为两个链表从相交点开始，后面的长度是一样的。让长链表先走掉多余的部分，剩下的路程就一样长了。
方法二：双指针法（推荐）
// 找到第一个相交节点
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == NULL || headB == NULL) return NULL;
int lenA = 0, lenB = 0;
ListNode* pA = headA;
ListNode* pB = headB;
// 计算链表A的长度
while (pA != NULL) {
lenA++;
pA = pA->next;
}
// 计算链表B的长度
while (pB != NULL) {
lenB++;
pB = pB->next;
}
// 让pA指向较长的链表，pB指向较短的
pA = headA;
pB = headB;
int diff = lenA - lenB;
if (diff > 0) {
// 链表A更长
while (diff--) {
pA = pA->next;
}
} else {
// 链表B更长
diff = -diff;
while (diff--) {
pB = pB->next;
}
}
// 一起走，直到相遇
while (pA != NULL && pB != NULL) {
if (pA == pB) {
return pA; // 找到相交节点
}
pA = pA->next;
pB = pB->next;
}
return NULL; // 没有相交
}小技巧：我曾经在写这个算法时，忘了处理 diff 为负数的情况。结果链表B比A长时，程序就崩了。后来我加了个绝对值处理，稳得很。
另一种巧妙解法：环形链表法
还有一种思路比较巧妙——把链表A的尾节点接到链表B的头节点上，如果形成了环，说明它们相交了。环的入口就是第一个相交节点。
不过我个人不太推荐这个方法，因为它会修改链表结构。在项目中，你改完链表还得恢复原状，万一忘了恢复，后面排查问题能让你怀疑人生。
知识结构图
下面这张图帮你理清链表相交问题的核心逻辑：
避坑指南
我曾经在写链表相交代码时，踩过几个坑，今天分享给你：
坑1：空链表处理 — 如果其中一个链表是空，那肯定不相交。代码里一定要先判空，否则访问 NULL->next 直接崩。
坑2：长度差计算 — diff 可能是负数，记得取绝对值。或者像我上面那样，用 if-else 分开处理。
坑3：死循环风险 — 双指针一起走时，一定要判断 pA 和 pB 是否为 NULL。如果链表不相交，它们会同时走到尾，然后退出循环。
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 是否修改链表 |
|---|---|---|---|
| 尾节点比较法 | O(m+n) | O(1) | 否 |
| 双指针法 | O(m+n) | O(1) | 否 |
| 环形链表法 | O(m+n) | O(1) | 是 |
从表格可以看出，双指针法在时间和空间上都是最优的，而且不修改链表结构。我个人强烈推荐在实际项目中使用它。
实际应用场景
链表相交问题在现实开发中挺常见的。我举几个例子：
- 内存池管理：多个内存链表可能共享同一块内存区域，需要判断是否相交以避免重复释放。
- 日志系统：多个日志链表可能共享历史记录，判断相交点可以优化存储。
- 图算法：在图的邻接表表示中，判断两条路径是否相交。
嗯，说白了，只要涉及到「共享节点」的场景，链表相交问题就会出现。掌握了今天讲的两种方法，你基本就能应对大部分情况了。
个人建议：面试时如果遇到链表相交问题，先问清楚「相交的定义是什么」。有些面试官会故意模糊概念，让你掉进「值相等就算相交」的坑里。先确认好定义，再动手写代码，这样显得你思路清晰。
好了，链表相交问题就讲到这里。代码不多，但逻辑需要想清楚。你可以在自己的编译器上跑一跑，试试不同的链表形态，加深理解。