相交链表问题的双指针解法与优化策略

1. 相交链表问题概述

相交链表是链表类题目中的经典问题，题目编号160。给定两个单链表的头节点 headA 和 headB，要求找出并返回两个单链表相交的起始节点。如果两个链表没有交点，则返回 null。

这个问题的难点在于：

• 两个链表可能在相交前有不同长度
• 需要设计时间复杂度为 O(m+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() 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(m+n) 空间复杂度：O(m)或O(n)

虽然时间复杂度达标，但空间复杂度不符合O(1)的要求。

3. 双指针最优解法

3.1 算法思路

最优解法使用双指针，核心思想是：

1. 指针pA从headA开始遍历，pB从headB开始遍历
2. 当pA到达链表末尾时，重定位到headB
3. 当pB到达链表末尾时，重定位到headA
4. 当pA和pB相遇时，即为相交节点

3.2 数学证明

设：

• 链表A不相交部分长度为a
• 链表B不相交部分长度为b
• 相交部分长度为c

则：

• pA走过的路径：a + c + b
• pB走过的路径：b + c + a 两者必然在相交点相遇（c≥0）或同时到达末尾（c=0）

3.3 代码实现

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

时间复杂度：O(m+n) 空间复杂度：O(1)

4. 边界条件与测试用例

4.1 常见边界情况

1. 两个链表都为空
2. 一个链表为空
3. 两个链表不相交
4. 两个链表完全重合
5. 相交点在第一个节点
6. 相交点在最后一个节点

4.2 测试用例示例

# 用例1：不相交 # 1->2->3 # 4->5 assert getIntersectionNode(headA1, headB1) == None # 用例2：在中间相交 # 1->2->3 # ↘ # 4->5 # ↗ # 6 assert getIntersectionNode(headA2, headB2).val == 4 # 用例3：一个链表为空 assert getIntersectionNode(headA3, None) == None

5. 实际应用与变种问题

5.1 实际应用场景

1. 内存管理：检测两个对象引用是否指向同一内存区域
2. 社交网络：查找两个用户的共同好友
3. 版本控制：查找两个分支的最近共同祖先

5.2 相关变种题目

1. 环形链表（LeetCode 141）
2. 环形链表II（LeetCode 142）
3. 合并两个有序链表（LeetCode 21）
4. 反转链表（LeetCode 206）

6. 性能优化与注意事项

6.1 优化技巧

1. 先计算两个链表长度，让长链表指针先走差值步
2. 使用位运算优化指针比较
3. 在内存受限环境下，可以考虑牺牲时间换空间

6.2 常见错误

1. 忘记处理链表为空的情况
2. 循环终止条件设置错误导致死循环
3. 指针移动顺序错误
4. 误认为节点值相同就是相交点（实际应比较节点对象）

7. 不同语言实现对比

7.1 C++实现

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA = headA, *pB = headB; while (pA != pB) { pA = pA ? pA->next : headB; pB = pB ? pB->next : headA; } return pA; }

7.2 Java实现

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pA = headA, pB = headB; while (pA != pB) { pA = (pA != null) ? pA.next : headB; pB = (pB != null) ? pB.next : headA; } return pA; }

7.3 JavaScript实现

var getIntersectionNode = function(headA, headB) { let pA = headA, pB = headB; while (pA !== pB) { pA = pA ? pA.next : headB; pB = pB ? pB.next : headA; } return pA; };

8. 链表问题解题通用思路

1. 画图辅助理解：可视化链表结构
2. 考虑双指针：快慢指针、前后指针等
3. 递归与迭代：根据场景选择合适方法
4. 虚拟头节点：简化边界条件处理
5. 反转链表：某些问题的关键步骤

对于相交链表问题，我个人的经验是：一定要先在纸上画出各种可能的情况，包括相交和不相交的场景，以及各种边界情况。双指针解法虽然巧妙，但如果不理解其背后的数学原理，很容易在面试中被问倒。在实际编码时，要特别注意指针移动的顺序和终止条件，这些都是容易出错的地方。