1. 相交链表问题概述
遇到链表相交问题时，很多初学者会陷入暴力解法的思维定式。实际上，这道题目考察的是对链表结构的深入理解和指针操作的巧妙运用。题目要求我们找出两个单链表相交的起始节点，如果不存在相交则返回null。
关键约束条件：
- 必须保持链表原始结构
- 时间复杂度O(n)
- 空间复杂度O(1)
2. 解法思路分析
2.1 暴力解法及其缺陷
最直观的解法是双重循环遍历：
def getIntersectionNode(headA, headB): pA = headA while pA: pB = headB while pB: if pA == pB: return pA pB = pB.next pA = pA.next return None时间复杂度O(mn)，空间复杂度O(1)。虽然满足空间要求，但时间复杂度过高，不适合实际应用。
2.2 哈希表法
改进思路是使用哈希表存储访问过的节点：
def getIntersectionNode(headA, headB): visited = set() while headA: visited.add(headA) headA = headA.next while headB: if headB in visited: return headB headB = headB.next return None时间复杂度O(m+n)，空间复杂度O(m)。虽然时间效率提升，但违反了空间复杂度要求。
2.3 双指针法（最优解）
真正满足题目要求的解法是双指针法。其核心思想是：
- 指针pA遍历链表A后继续遍历链表B
- 指针pB遍历链表B后继续遍历遍历链表A
- 两指针相遇时即为相交节点
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. 算法正确性证明
设链表A独有部分长度为a，链表B独有部分长度为b，公共部分长度为c。
双指针遍历路径：
- pA路径：a + c + b
- pB路径：b + c + a
当a + c + b == b + c + a时，两指针必然相遇：
- 若相交：在第一个公共节点相遇
- 不相交：同时到达None
4. 边界条件处理
实际编码时需要注意：
- 输入为None的情况
- 完全不相交的链表
- 一个链表完全包含另一个链表
- 链表存在环的情况（题目已说明无环）
5. 复杂度分析
时间复杂度：O(m+n) 空间复杂度：O(1) 完全满足题目要求。
6. 同类问题扩展
类似思路可解决：
- 判断链表是否有环
- 寻找链表中间节点
- 判断回文链表
掌握这种双指针技巧对解决链表问题大有裨益。建议读者可以尝试用相同思路解决LeetCode 141（环形链表）和142（环形链表II）来巩固这一技巧。
