1. 链表相交问题的整体解题思路拆解单链表相交这个问题表面上看是一道算法题但它在实际面试中出现的频率极高原因不在于题目本身有多难而在于它能同时考察候选人对指针操作、空间复杂度意识、边界条件处理三个维度的理解深度。我面过不少人简历上写着精通数据结构结果连“两个链表相交后为什么一定呈Y形而不是X形”都说不清楚这就很能说明问题了。先把问题定义清楚给定两个单链表的头指针判断它们是否相交如果相交找出第一个公共节点。这里的“相交”指的是节点级别的共享也就是两个链表从某个节点开始后续所有节点都是同一个物理节点而不是值相等。这一点是很多初学者容易搞混的地方必须在一开始就明确。为什么这个区分如此重要因为如果只是值相等那问题就退化成“找两个链表中第一个值相同的节点”用哈希表或者暴力双重循环都能做难度直线下降。但节点级共享意味着内存地址相同这就引出了一个关键性质两个链表一旦相交从交点开始到链表尾部它们共享同一段内存因此这段路径的长度对两个链表来说是完全一样的。这个性质直接决定了整个问题的解法方向。你可以这样理解把两个链表想象成两条路它们在某个路口汇合汇合之后就只有一条路了。所以两条路的总长度可能不同但汇合点到终点的距离是相同的。基于这个认知所有高效解法都是围绕“如何让两个指针同时到达交点”来设计的。从面试官的角度来看这道题通常有三个层次的期望及格线能写出暴力解法双重循环时间复杂度O(m*n)空间复杂度O(1)。这只能说明你会写代码但不会优化。良好线能用哈希表记录第一个链表的所有节点然后遍历第二个链表找第一个命中项。时间O(mn)空间O(m)。这说明你有空间换时间的意识。优秀线能用双指针法做到时间O(mn)、空间O(1)。这才是这道题的标准答案也是面试官真正想看到的。下面我会把这三个层次的解法都拆开讲清楚重点放在双指针法的推导过程和实现细节上因为这是面试中最常被追问的部分。2. 核心细节解析与实操要点2.1 为什么相交链表一定是Y形而不是X形这个问题我在面试中问过不下二十次能答对的人不到一半。原因其实很简单单链表的每个节点只有一个next指针。假设两个链表在某个节点相交后又分开了那就意味着这个公共节点有两个不同的next指针这直接违反了单链表的定义。所以一旦相交从交点开始到尾部两个链表共享的路径是完全重合的。这就形成了一个Y字形或者更准确地说是一个横过来的Y。这个性质是所有高效解法的基础不理解这一点后面的双指针法就无从谈起。注意有些面试官会故意把题目说成“两个链表可能相交也可能不相交”这时候你需要在算法中同时处理两种情况不能默认它们一定相交。2.2 双指针法的核心推导过程双指针法的思路可以用一句话概括让两个指针走相同的总路程它们必然同时到达交点。具体推导如下设链表A的独立部分长度为a链表B的独立部分长度为b公共部分长度为c。指针pA从A的头出发走完A的独立部分a步后进入公共部分再走c步到达尾部总路程为ac。指针pB从B的头出发走完B的独立部分b步后进入公共部分再走c步到达尾部总路程为bc。现在关键操作来了当pA走到尾部NULL时让它从B的头重新出发当pB走到尾部时让它从A的头重新出发。pA的总路程变为a c bpB的总路程变为b c a两者相等。也就是说如果两个链表相交pA和pB会在走完abc步后同时到达交点。如果两个链表不相交它们会同时到达NULL此时返回NULL即可。这个推导的美妙之处在于你不需要知道a、b、c的具体值也不需要先遍历一遍求长度差。代码实现极其简洁def getIntersectionNode(headA, headB): if not headA or not headB: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA这段代码的精妙之处在于它把“不相交”和“相交”两种情况统一处理了。不相交时pA和pB最终都会变成NULL循环条件pA ! pB不成立返回NULL。相交时它们会在交点处相遇返回交点。2.3 长度差法的实现细节除了双指针法另一种常见的O(1)空间解法是长度差法。思路也很直观先分别遍历两个链表求出长度lenA和lenB。计算长度差diff |lenA - lenB|。让较长的链表指针先走diff步。然后两个指针同时走直到相遇或同时到达NULL。这个方法的正确性依赖于前面说的Y形性质对齐尾部后两个指针距离交点的距离相同。def getIntersectionNode(headA, headB): lenA, lenB 0, 0 pA, pB headA, headB while pA: lenA 1 pA pA.next while pB: lenB 1 pB pB.next pA, pB headA, headB if lenA lenB: for _ in range(lenA - lenB): pA pA.next else: for _ in range(lenB - lenA): pB pB.next while pA ! pB: pA pA.next pB pB.next return pA两种方法的时间复杂度都是O(mn)空间复杂度都是O(1)。双指针法代码更短但长度差法的思路更直观面试时可以根据面试官的偏好选择。2.4 哈希表法的适用场景哈希表法的思路最简单遍历链表A把所有节点存入一个集合然后遍历链表B第一个在集合中出现的节点就是交点。def getIntersectionNode(headA, headB): visited set() pA headA while pA: visited.add(pA) pA pA.next pB headB while pB: if pB in visited: return pB pB pB.next return None这个方法的时间复杂度是O(mn)空间复杂度是O(m)。虽然空间不是最优但在实际工程中如果链表长度不大或者代码可读性比空间更重要这个方法完全可以用。面试时如果面试官没有特别要求O(1)空间先说出哈希表法再优化到双指针法反而能体现你的思维递进过程。3. 实操过程与核心环节实现3.1 完整可运行的代码实现下面我给出一个完整的、包含测试用例的Python实现。这段代码可以直接复制运行方便你验证自己的理解。class ListNode: def __init__(self, val0): self.val val self.next None def getIntersectionNode(headA, headB): 双指针法求两个单链表的交点 时间复杂度O(mn)空间复杂度O(1) if not headA or not headB: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA def build_intersecting_lists(): 构造测试用例 链表A: 1 - 2 - 3 - 6 - 7 - 8 链表B: 4 - 5 - 6 - 7 - 8 交点为值为6的节点 common ListNode(6) common.next ListNode(7) common.next.next ListNode(8) headA ListNode(1) headA.next ListNode(2) headA.next.next ListNode(3) headA.next.next.next common headB ListNode(4) headB.next ListNode(5) headB.next.next common return headA, headB, common def build_non_intersecting_lists(): 构造不相交的测试用例 headA ListNode(1) headA.next ListNode(2) headA.next.next ListNode(3) headB ListNode(4) headB.next ListNode(5) return headA, headB if __name__ __main__: # 测试相交情况 headA, headB, expected build_intersecting_lists() result getIntersectionNode(headA, headB) print(f相交测试: 期望交点值{expected.val}, 实际{result.val if result else None}) # 测试不相交情况 headA, headB build_non_intersecting_lists() result getIntersectionNode(headA, headB) print(f不相交测试: 期望None, 实际{result})运行结果应该是相交测试: 期望交点值6, 实际6 不相交测试: 期望None, 实际None3.2 边界条件处理清单这道题的边界条件特别多面试时如果考虑不全很容易被扣分。我整理了一份清单建议你在写代码前先过一遍边界情况处理方式容易犯的错误任一链表为空直接返回None忘记判空导致空指针异常两个链表都不为空但不相交双指针最终都变成NULL返回NULL循环条件写成while pA and pB导致死循环交点就是第一个节点双指针第一次比较就相等直接返回无两个链表完全相同返回第一个节点无其中一个链表是另一个的子串返回子串的起始节点长度差法中对齐时算错步数链表中存在环这道题默认无环但面试官可能追问需要先判断是否有环提示如果面试官追问“如果链表可能有环怎么办”你需要先分别判断两个链表是否有环然后分情况讨论。两个都有环、一个有一个没有、两个都无环每种情况的处理方式不同。这是这道题的进阶版本后面我会详细讲。3.3 双指针法的执行过程模拟为了让你彻底理解双指针法我用前面构造的测试用例手动模拟一遍执行过程。链表A1 - 2 - 3 - 6 - 7 - 8 链表B4 - 5 - 6 - 7 - 8初始化pA指向1pB指向4。步数pA位置pB位置说明014初始状态125同时前进236pB到达交点367pA到达交点但pB已经过了478同时前进58NULLpB到达尾部6NULL1pA到达尾部pB切换到A的头742pA切换到B的头853同时前进966相遇返回交点可以看到pA走了3339步pB走了3339步总路程相同最终在交点相遇。3.4 长度差法的执行过程模拟同样用上面的测试用例遍历A得到lenA6遍历B得到lenB5。diff1pA先走1步指向2。pA从2开始pB从4开始同时前进pA2, pB4pA3, pB5pA6, pB6相遇返回交点。两种方法殊途同归但双指针法的代码更简洁不需要额外的长度计算步骤。4. 常见问题与排查技巧实录4.1 面试中最容易踩的五个坑坑一把值相等当成节点相等。这是最致命的错误。有些候选人看到两个链表中有相同的值就认为相交了完全忽略了内存地址的概念。面试官只要构造两个值相同但地址不同的节点就能立刻识破。坑二循环条件写错导致死循环。双指针法中循环条件是while pA ! pB而不是while pA and pB。如果写成后者当两个链表不相交时pA和pB最终都会变成NULL循环条件不成立但此时你还没有返回结果逻辑就断了。坑三切换链表头时忘记判空。pA pA.next if pA else headB这个三元表达式必须写完整。如果写成pA pA.next if pA.next else headB当pA本身是NULL时会直接崩溃。坑四长度差法中对齐时走错步数。有些人在计算diff后让长链表先走diff步但diff算错了比如用了lenA - lenB而不是abs(lenA - lenB)导致两个指针永远错位。坑五忽略链表为空的边界情况。如果headA或headB为NULL直接返回NULL。这个判断必须放在最前面否则后面的代码会出问题。4.2 面试官追问的进阶问题追问一如果链表可能有环怎么判断相交这个问题比原题难一个档次。你需要分三步走分别判断两个链表是否有环用快慢指针法。如果两个都无环用原题的双指针法。如果两个都有环先找到各自的入环点。如果入环点相同说明它们在环之前就相交了交点可以用无环的方法找如果入环点不同需要判断一个链表的入环点是否在另一个链表的环上如果在则相交交点就是那个入环点如果不在则不相交。如果一个有环一个无环直接不相交。追问二如何在不遍历链表的情况下判断是否相交如果只判断是否相交而不求交点有一个更简单的方法分别遍历两个链表到尾部如果尾节点是同一个节点则相交否则不相交。时间复杂度O(mn)空间O(1)。但这个方法只能判断是否相交不能求交点。追问三如果链表长度非常大双指针法会不会超时不会。双指针法的时间复杂度是O(mn)无论链表多长每个指针最多走mn步。即使链表有百万个节点在现代计算机上也是毫秒级完成。4.3 常见问题速查表问题现象可能原因解决方法程序崩溃空指针异常没有判空在函数开头加if not headA or not headB: return None死循环循环条件写错确保循环条件是while pA ! pB返回了错误的交点把值相等当成节点相等用is或比较节点对象而不是比较val不相交时返回了非NULL切换链表头时逻辑错误检查三元表达式是否正确处理了NULL情况长度差法结果错误diff计算错误用abs(lenA - lenB)确保diff非负两个链表完全相同但返回NULL循环条件在第一次比较前就退出了检查初始化是否正确4.4 我个人的实操心得这道题我刷过不下十遍也用它面过很多人。有几个心得值得分享第一先沟通再写代码。面试时不要一上来就闷头写先跟面试官确认“相交是指节点级共享还是值相等”这个确认动作本身就能加分。很多候选人觉得这是废话但面试官往往就是在等这个问题。第二先说思路再写代码。你可以这样说“我首先想到的是哈希表法时间O(mn)空间O(m)但空间不是最优。优化一下可以用双指针法做到O(1)空间核心思路是让两个指针走相同的总路程。”这样面试官就知道你不仅会写还理解背后的权衡。第三手动模拟一遍。写完代码后不要直接说“写完了”而是用一个简单的例子手动走一遍确认边界条件都处理了。这个习惯能帮你发现80%的bug。第四准备进阶问题的答案。有环的情况、只判断不相交的情况、链表长度极大的情况这些都提前想清楚。面试官一旦追问你能对答如流印象分直接拉满。第五代码风格要干净。变量命名用pA、pB而不是p1、p2注释写清楚每一步的意图。面试官看代码的时间可能比你写代码的时间还长可读性很重要。最后再分享一个小技巧如果你在面试中一时想不出双指针法可以先写哈希表法然后说“这个方法空间是O(m)我想优化到O(1)”。这样即使你最终没写出最优解面试官也会认为你有优化意识比直接卡壳强得多。