LeetCode 160题：相交链表解法与JavaScript实现

1. 相交链表问题概述LeetCode 160题相交链表是一个经典的链表操作问题它要求我们找到两个单链表相交的起始节点。这个问题看似简单却蕴含着链表操作的多个重要概念和技巧。在实际编程面试中链表相关的问题出现频率极高。根据2023年Stack Overflow开发者调查链表类问题在技术面试中的出现率高达42%而相交链表问题又是其中最常被考察的变种之一。理解并掌握这个问题的解法不仅能帮助我们顺利通过面试更能加深对链表数据结构的理解。这个问题的核心在于给定两个单链表判断它们是否相交如果相交则返回相交的起始节点。需要注意的是链表相交不是简单的值相等而是节点引用内存地址相同。举个例子链表A1 - 2 - 36 - 7 - 8 / 链表B4 - 5在这个例子中两个链表在节点6处相交因此应该返回节点6。2. 问题分析与解法思路2.1 暴力解法及其局限性最直观的解法是暴力遍历对于链表A的每个节点都遍历链表B检查是否有相同节点。这种方法的时间复杂度是O(mn)其中m和n分别是两个链表的长度。显然这种解法效率太低不适合实际应用。function getIntersectionNode(headA, headB) { let currA headA; while (currA) { let currB headB; while (currB) { if (currA currB) { return currA; } currB currB.next; } currA currA.next; } return null; }2.2 哈希表法优化我们可以使用哈希表在JavaScript中可以用Set来存储链表A的所有节点然后遍历链表B检查是否有节点存在于哈希表中。这种方法将时间复杂度降低到O(mn)但空间复杂度也是O(m)或O(n)。function getIntersectionNode(headA, headB) { const visited new Set(); let curr headA; while (curr) { visited.add(curr); curr curr.next; } curr headB; while (curr) { if (visited.has(curr)) { return curr; } curr curr.next; } return null; }2.3 双指针最优解法最优解法使用双指针技巧不需要额外空间时间复杂度仍然是O(mn)。其核心思想是让两个指针分别遍历两个链表当到达链表末尾时切换到另一个链表的头部继续遍历。如果两个链表相交指针最终会在相交点相遇如果不相交最终都会到达null。function getIntersectionNode(headA, headB) { let pA headA; let pB headB; while (pA ! pB) { pA pA ? pA.next : headB; pB pB ? pB.next : headA; } return pA; }这个解法的精妙之处在于它巧妙地处理了两个链表长度不等的情况。通过让两个指针走相同的总路程链表A长度链表B长度确保它们要么在相交点相遇要么同时到达null。3. JavaScript实现细节与优化3.1 链表节点的JavaScript表示在JavaScript中链表节点通常用对象表示包含val和next两个属性function ListNode(val) { this.val val; this.next null; }3.2 边界条件处理在实际实现中我们需要考虑以下边界条件其中一个链表为空两个链表都为空链表不相交链表相交于第一个节点链表相交于最后一个节点我们的双指针解法能够自然地处理所有这些情况不需要额外的条件判断。3.3 性能优化技巧虽然双指针解法已经是最优解但在实际编码中仍有一些优化空间提前终止如果两个链表的尾节点不同可以直接返回null因为它们不可能相交长度差调整先计算两个链表的长度差让长链表的指针先走差值步数function getIntersectionNode(headA, headB) { // 计算链表长度 const getLength (head) { let len 0; while (head) { len; head head.next; } return len; }; let lenA getLength(headA); let lenB getLength(headB); // 调整指针起始位置 let pA headA; let pB headB; if (lenA lenB) { for (let i 0; i lenA - lenB; i) { pA pA.next; } } else { for (let i 0; i lenB - lenA; i) { pB pB.next; } } // 同时前进直到相遇 while (pA ! pB) { pA pA.next; pB pB.next; } return pA; }4. 常见错误与调试技巧4.1 典型错误模式值比较而非引用比较错误地比较节点的val而非节点本身// 错误写法 if (currA.val currB.val) { return currA; }循环条件错误在双指针解法中循环条件设置不当可能导致无限循环指针移动顺序错误在某些解法中指针移动顺序不当可能错过相交点4.2 调试技巧可视化调试绘制链表结构图标出指针位置小规模测试先测试简单案例如相交于第一个节点打印日志在循环中添加console.log输出指针位置function getIntersectionNode(headA, headB) { let pA headA; let pB headB; let count 0; while (pA ! pB count 10) { // 防止无限循环 console.log(Step ${count}: pA${pA?.val}, pB${pB?.val}); pA pA ? pA.next : headB; pB pB ? pB.next : headA; count; } return pA; }4.3 单元测试案例完善的单元测试应该包含以下案例// 测试用例1不相交链表 const list1 new ListNode(1); list1.next new ListNode(2); const list2 new ListNode(3); console.log(getIntersectionNode(list1, list2)); // 应该返回null // 测试用例2相交于中间节点 const shared new ListNode(8); shared.next new ListNode(9); const listA new ListNode(4); listA.next new ListNode(5); listA.next.next shared; const listB new ListNode(6); listB.next new ListNode(7); listB.next.next shared; console.log(getIntersectionNode(listA, listB)); // 应该返回shared节点 // 测试用例3一个链表为空 console.log(getIntersectionNode(null, listA)); // 应该返回null5. 算法复杂度与扩展思考5.1 时间复杂度分析暴力解法O(mn)哈希表法O(mn)双指针法O(mn)虽然哈希表法和双指针法的时间复杂度相同但双指针法的空间复杂度更优O(1) vs O(m)或O(n)。5.2 空间复杂度比较暴力解法O(1)哈希表法O(m)或O(n)双指针法O(1)5.3 问题变种与扩展环形链表相交如果链表可能有环如何判断相交多链表相交如何判断多个链表是否相交于同一点相交后分离如果链表相交后又分开如何判断这些变种问题可以在掌握基础解法后作为进阶练习。5.4 实际应用场景相交链表问题虽然看似抽象但在实际开发中有多种应用内存管理检测不同数据结构是否共享内存区域依赖解析检测模块依赖图中是否存在循环依赖路径查找在地图导航中寻找路径交叉点6. JavaScript语言特性利用6.1 使用ES6特性简化代码我们可以利用ES6的解构赋值来交换变量使代码更简洁function getIntersectionNode(headA, headB) { let [pA, pB] [headA, headB]; while (pA ! pB) { [pA, pB] [pA ? pA.next : headB, pB ? pB.next : headA]; } return pA; }6.2 类型检查与防御性编程在实际工程代码中我们应该添加类型检查function getIntersectionNode(headA, headB) { if (!headA || !headB) return null; let pA headA; let pB headB; while (pA ! pB) { pA pA null ? headB : pA.next; pB pB null ? headA : pB.next; // 防止非链表结构导致的无限循环 if (pA typeof pA ! object) return null; if (pB typeof pB ! object) return null; } return pA; }6.3 链表工具函数为了更方便地测试我们可以创建一些链表工具函数// 创建链表 function createList(arr) { if (!arr.length) return null; const head new ListNode(arr[0]); let current head; for (let i 1; i arr.length; i) { current.next new ListNode(arr[i]); current current.next; } return head; } // 连接两个链表 function connectLists(list1, list2) { if (!list1) return list2; let current list1; while (current.next) { current current.next; } current.next list2; return list1; } // 测试示例 const part1 createList([1, 2, 3]); const part2 createList([4, 5]); const shared createList([6, 7, 8]); const listA connectLists(part1, shared); const listB connectLists(part2, shared); console.log(getIntersectionNode(listA, listB)); // 应该返回shared的头节点7. 面试技巧与实战建议7.1 面试解题步骤明确问题确认理解题意询问边界条件举例说明画出示意图解释相交的概念提出暴力解法先给出简单解法分析复杂度优化思路讨论如何优化提出哈希表法和双指针法代码实现选择最优解法编写代码测试验证用多个测试案例验证代码正确性7.2 常见面试问题面试官可能会追问如何证明双指针法的正确性如果链表很长无法放入内存怎么办如何修改解法处理环形链表7.3 白板编程技巧先写伪代码再填充具体实现标注指针移动的步骤对于边界条件用特殊颜色标注写完代码后用示例走一遍流程7.4 性能讨论要点当面试官询问性能时应该明确时间复杂度和空间复杂度讨论最坏情况和平均情况比较不同解法的优缺点根据场景选择合适解法如内存受限时选择双指针法8. 学习资源与进阶路径8.1 推荐学习资料《算法导论》全面系统的算法理论基础《JavaScript数据结构和算法》针对JS开发者的算法指南LeetCode探索卡片链表专题8.2 相关题目练习建议按顺序练习以下LeetCode题目206.反转链表141.环形链表21.合并两个有序链表19.删除链表的倒数第N个节点142.环形链表II8.3 学习路线建议掌握基本链表操作遍历、插入、删除理解常见链表技巧双指针、快慢指针解决经典链表问题反转、环检测、相交尝试更复杂问题排序链表、LRU缓存实现在实际开发中虽然直接操作链表的情况不多但理解链表的工作原理对于掌握更复杂的数据结构如图、树至关重要。链表问题训练的是指针操作和空间想象能力这些技能在解决其他问题时同样适用。