尧图网站建设 
1. 相交链表问题概述相交链表是链表类题目中的经典问题题目编号160。给定两个单链表的头节点 headA 和 headB要求找出并返回两个单链表相交的起始节点。如果两个链表没有交点则返回 null。这个问题的难点在于两个链表可能在相交前有不同长度需要设计时间复杂度为 O(mn)、空间复杂度为 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(mn) 空间复杂度O(m)或O(n)虽然时间复杂度达标但空间复杂度不符合O(1)的要求。3. 双指针最优解法3.1 算法思路最优解法使用双指针核心思想是指针pA从headA开始遍历pB从headB开始遍历当pA到达链表末尾时重定位到headB当pB到达链表末尾时重定位到headA当pA和pB相遇时即为相交节点3.2 数学证明设链表A不相交部分长度为a链表B不相交部分长度为b相交部分长度为c则pA走过的路径a c bpB走过的路径b c a 两者必然在相交点相遇c≥0或同时到达末尾c03.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(mn) 空间复杂度O(1)4. 边界条件与测试用例4.1 常见边界情况两个链表都为空一个链表为空两个链表不相交两个链表完全重合相交点在第一个节点相交点在最后一个节点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) None5. 实际应用与变种问题5.1 实际应用场景内存管理检测两个对象引用是否指向同一内存区域社交网络查找两个用户的共同好友版本控制查找两个分支的最近共同祖先5.2 相关变种题目环形链表LeetCode 141环形链表IILeetCode 142合并两个有序链表LeetCode 21反转链表LeetCode 2066. 性能优化与注意事项6.1 优化技巧先计算两个链表长度让长链表指针先走差值步使用位运算优化指针比较在内存受限环境下可以考虑牺牲时间换空间6.2 常见错误忘记处理链表为空的情况循环终止条件设置错误导致死循环指针移动顺序错误误认为节点值相同就是相交点实际应比较节点对象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. 相交链表问题概述相交链表是链表类题目中的经典问题题目编号160。给定两个单链表的头节点 headA 和 headB要求找出并返回两个单链表相交的起始节点。如果两个链表没有交点则返回 null。这个问题的难点在于两个链表可能在相交前有不同长度需要设计时间复杂度为 O(mn)、空间复杂度为 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(mn) 空间复杂度O(m)或O(n)虽然时间复杂度达标但空间复杂度不符合O(1)的要求。3. 双指针最优解法3.1 算法思路最优解法使用双指针核心思想是指针pA从headA开始遍历pB从headB开始遍历当pA到达链表末尾时重定位到headB当pB到达链表末尾时重定位到headA当pA和pB相遇时即为相交节点3.2 数学证明设链表A不相交部分长度为a链表B不相交部分长度为b相交部分长度为c则pA走过的路径a c bpB走过的路径b c a 两者必然在相交点相遇c≥0或同时到达末尾c03.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(mn) 空间复杂度O(1)4. 边界条件与测试用例4.1 常见边界情况两个链表都为空一个链表为空两个链表不相交两个链表完全重合相交点在第一个节点相交点在最后一个节点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) None5. 实际应用与变种问题5.1 实际应用场景内存管理检测两个对象引用是否指向同一内存区域社交网络查找两个用户的共同好友版本控制查找两个分支的最近共同祖先5.2 相关变种题目环形链表LeetCode 141环形链表IILeetCode 142合并两个有序链表LeetCode 21反转链表LeetCode 2066. 性能优化与注意事项6.1 优化技巧先计算两个链表长度让长链表指针先走差值步使用位运算优化指针比较在内存受限环境下可以考虑牺牲时间换空间6.2 常见错误忘记处理链表为空的情况循环终止条件设置错误导致死循环指针移动顺序错误误认为节点值相同就是相交点实际应比较节点对象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. 链表问题解题通用思路画图辅助理解可视化链表结构考虑双指针快慢指针、前后指针等递归与迭代根据场景选择合适方法虚拟头节点简化边界条件处理反转链表某些问题的关键步骤对于相交链表问题我个人的经验是一定要先在纸上画出各种可能的情况包括相交和不相交的场景以及各种边界情况。双指针解法虽然巧妙但如果不理解其背后的数学原理很容易在面试中被问倒。在实际编码时要特别注意指针移动的顺序和终止条件这些都是容易出错的地方。