1. 链表相交问题背景与核心挑战链表相交问题是数据结构与算法中的经典题型在LeetCode上被标记为简单难度但实际面试中出现频率极高。这道题考察的是对链表结构的理解以及双指针技巧的灵活运用。链表相交的定义是两个链表在某个节点开始合并后续所有节点都相同。注意区分节点值相同和节点对象相同的区别——题目要求的是物理内存地址相同的节点而非仅仅数值相等。举个例子链表A1→2→3→4→5链表B9→8→3→4→5 这里的交点是值为3的节点假设两个3是同一个内存对象这个问题看似简单但隐藏着几个关键挑战链表长度可能不同无法直接对齐比较需要O(1)的空间复杂度不能使用哈希表等额外存储需要处理各种边界条件如无交点、链表为空等2. 暴力解法与哈希表方案分析2.1 暴力匹配法最直观的解法是双重循环遍历链表A的每个节点对于每个节点再遍历链表B查找相同节点。这种方法时间复杂度为O(mn)空间复杂度O(1)在LeetCode上会超时。def getIntersectionNode(headA, headB): pA headA while pA: pB headB while pB: if pA pB: return pA pB pB.next pA pA.next return None2.2 哈希表存储方案另一种思路是用哈希表存储链表A的所有节点然后检查链表B的节点是否存在于哈希表中。这种方法时间复杂度O(mn)空间复杂度O(m)或O(n)。def getIntersectionNode(headA, headB): nodes set() while headA: nodes.add(headA) headA headA.next while headB: if headB in nodes: return headB headB headB.next return None虽然这个方案可以通过LeetCode测试但不符合题目要求的O(1)空间复杂度。面试时如果只给出这个方案通常会被要求进一步优化。3. 双指针法的精妙设计3.1 基本思路最优解采用双指针法核心思想是让两个指针走过相同的总路径长度。具体步骤指针pA从链表A头部开始pB从链表B头部开始每次同时移动pA和pB一步当pA到达链表A末尾时让它从链表B头部重新开始当pB到达链表B末尾时让它从链表A头部重新开始当pA和pB相遇时就是交点或者都为None表示无交点def getIntersectionNode(headA, headB): pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA3.2 数学原理证明假设链表A独有部分长度为a链表B独有部分长度为b公共部分长度为c双指针走过的路径长度均为a b cpA路径a → c → bpB路径b → c → a如果无交点c0则最终pA和pB会同时为None循环终止。3.3 边界条件处理这个算法自动处理了各种边界情况一个链表为空立即返回None两个链表都为空立即返回None无交点最终pA和pB都为None交点在头部第一次比较就能发现4. 算法优化与变种问题4.1 提前计算长度法另一种O(1)空间的方法是先计算两个链表的长度差然后让长链表的指针先移动差值步数再同时移动比较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这种方法在链表很长但交点靠近末尾时性能更好因为避免了多余的遍历。4.2 变种问题判断链表是否有环类似的双指针技巧快慢指针可以用来判断链表是否有环这也是面试常见题def hasCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False5. 实际面试中的考察要点在技术面试中面试官通常会期待候选人能够快速给出暴力解法并分析其复杂度能提出哈希表方案并意识到空间复杂度的不足最终给出双指针方案并解释其数学原理处理各种边界条件的能力对时间/空间复杂度的准确分析常见follow-up问题包括如果链表可能有环怎么办如何修改算法使其适用于循环链表如果只能改变链表结构不能使用额外空间怎么办6. 代码实现中的注意事项6.1 Python实现细节在Python中需要注意节点对象的比较方式。正确的做法是比较节点对象本身而不是节点的值# 正确 if nodeA nodeB: # 错误可能误判 if nodeA.val nodeB.val:6.2 测试用例设计完整的测试应该包括常规相交情况无交点情况一个链表为空交点在头部交点在尾部两个链表完全相同长链表与短链表相交6.3 复杂度分析双指针法时间复杂度O(mn)空间复杂度O(1)这是最优解因为每个链表最多被遍历两次。7. 同类问题拓展练习为了巩固双指针技巧建议练习以下LeetCode题目环形链表判断链表是否有环环形链表 II找到环的起点删除链表的倒数第N个节点链表的中间结点特别是环形链表问题与本题有异曲同工之妙都利用了指针走过的路径长度关系。