大家好，我是陆砚码。今天我们来聊聊LeetCode上的一个经典题目：如何找到两个单链表相交的起始节点？
📌 题目描述
给你两个单链表的头节点headA和headB，找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
进阶挑战：能否设计一个时间复杂度O(N)、仅用O(1)内存的解决方案？
💡 破题思路：走过你走过的路
首先，我们可以排除使用哈希表的方法，因为它的空间复杂度是O(N)，不符合题目的要求。那么，我们该如何解决这个问题呢？
关键在于，两个链表相交后的尾部是完全一样的。他们之所以不能同时到达相交点，仅仅是因为前面的独立长度不一样。
于是，我们可以使用一个绝妙的“路程互补”算法：定义两个指针pA和pB，分别从headA和headB出发。每人每次走一步。当pA走到底（null）时，让它从headB重新开始走。当pB走到底（null）时，让它从headA重新开始走。
为什么这样一定行？假设链表 A 的独立部分长度为 a，链表 B 的独立部分长度为 b，相交部分长度为 c。
pA走过的路程：a+c+bpB走过的路程：b+c+a
两人走过的总长度完全一样！所以他们最终一定会同时走到那个相交的起点。如果根本不相交（c=0），那他们俩就会在走了 a+b 步之后，双双变成null并在虚无中相遇，代码同样完美成立。
💻 C++ 代码实现 (极简双指针法)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 如果有任何一个链表为空，绝不可能相交
if (!headA || !headB) return nullptr;
ListNode *pA = headA;
ListNode *pB = headB;
// 只要两人没相遇，就一直走
while (pA != pB) {
// pA 走完了，就跳到 B 链表头；否则继续走
pA = pA == nullptr ? headB : pA->next;
// pB 走完了，就跳到 A 链表头；否则继续走
pB = pB == nullptr ? headA : pB->next;
}
// 相遇点就是相交节点（如果不相交，这里正好返回 nullptr）
return pA;
}
};
这就是我们的解决方案，简单又高效。如果你对这个问题还有疑问，或者想了解更多关于链表的操作，欢迎访问思享编程网（www.sxgpb.com）了解更多内容。