LCR 171.链表中第一个公共节点
难度：🟢 简单
标签：哈希表、链表、双指针
链接：LCR 171. 链表中第一个公共节点 (剑指 Offer 52. 两个链表的第一个公共节点)
题目描述
给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则必须从相交节点开始往后完全相同）。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：两个链表不相交，因此返回 null 。
解题思路
核心思想
本题最巧妙的解法是利用 双指针 走过相同的路程，最终在相交点相遇。我们可以设想有两个人（指针 pA 和 pB）分别从两条链表的头节点 headA 和 headB 出发。当一个人走完自己的路（到达 null）时，就立刻切换到对方的起点继续走。
pA的路径：A 链->B 链pB的路径：B 链->A 链
如果两个链表相交，设 A 的非相交部分长度为 a，B 的非相交部分长度为 b，相交部分长度为 c。那么：
pA走a+c到达相交点时，pB走了b+c。pA切换到headB后，再走b步到达相交点，总路程为a+c+b。pB切换到headA后，再走a步到达相交点，总路程为b+c+a。 因为总路程相同，所以它们必然会在相交点相遇。如果两链表不相交，他们会同时走完A链+B链的长度，最终同时变为null并在null处“相遇”。
思路选择
双指针法 是解决此问题的最优解，因为它空间复杂度为 O(1)，且代码非常简洁优雅。
关键步骤
处理边界情况：如果任一链表为空，则不可能相交，返回
null。初始化指针：创建两个指针，
pA = headA和pB = headB。循环遍历：当
pA和pB不相等时，持续循环。 a. 移动pA：如果pA不为null，则pA = pA.next；如果pA为null（走完了 A 链），则让它切换到 B 链的头部，即pA = headB。 b. 移动pB：如果pB不为null，则pB = pB.next；如果pB为null（走完了 B 链），则让它切换到 A 链的头部，即pB = headA。返回结果：当循环结束时，
pA和pB相等，此时它们共同指向的节点就是相交节点。如果两链表不相交，它们会同时变为null，此时返回null也符合题意。
代码实现
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
if (headA === null || headB === null) {
return null;
}
let pA = headA, pB = headB;
while (pA !== pB) {
// 如果 pA 到达末尾，则切换到 headB；否则，走一步
pA = pA ? pA.next : headB;
// 如果 pB 到达末尾，则切换到 headA；否则，走一步
pB = pB ? pB.next : headA;
}
// 返回相遇点，如果无交点，则此时 pA 和 pB 都为 null
return pA;
};
复杂度分析
时间复杂度：O(m + n) 其中 m 和 n 分别是两个链表的长度。在最坏的情况下（无交点），每个指针都需要遍历两个链表一次。
空间复杂度：O(1) 我们只使用了
pA和pB两个额外指针，空间消耗是恒定的。
相关题目
总结
本题的双指针解法是一个非常精妙的设计，它通过让两个指针走过“对称”的路径 (A+B 和 B+A) 来消除长度差，从而保证它们如果能在非 null 处相遇，该点必然是第一个交点。这个思路值得深入理解和学习。