1. Leetcode 160题解析用JavaScript搞定相交链表问题今天我们来啃Leetcode第160题——相交链表Intersection of Two Linked Lists。这道题在面试中出现的频率相当高根据我的面试官经验至少有30%的候选人会在这道基础链表题上栽跟头。作为JavaScript开发者掌握链表操作是基本功这道题正好能检验你对指针引用操作的理解深度。这道题的要求很简单给定两个单链表的头节点headA和headB找出并返回两个链表相交的起始节点。如果没有交点返回null。题目有个特别要求你必须在O(n)时间复杂度和O(1)内存复杂度下解决这个问题。2. 问题分析与解法思路2.1 理解链表相交的本质首先我们需要明确什么是链表相交。不是简单的值相同而是节点对象相同——即两个链表在某个节点开始合并成一条链表。比如// 链表A1 - 2 - 3 // \ // 6 - 7 // / // 链表B4 - 5这里节点6就是相交节点。注意相交节点之后的链表部分是共享的这也是解题的关键线索。2.2 暴力解法及其局限最直观的解法是双重循环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; }这种解法时间复杂度是O(mn)空间复杂度O(1)显然不符合题目要求。我们需要更聪明的办法。2.3 最优解双指针走天涯法这道题的经典解法是使用双指针技巧。基本思路是指针pA从headA开始pB从headB开始每次各走一步当pA走到末尾时让它从headB重新开始当pB走到末尾时让它从headA重新开始两者相遇的节点就是交点或者都走到null表示无交点为什么这个方法有效因为两个指针走过的总路程相同AB的长度最终会在交点相遇。3. JavaScript实现详解3.1 基础实现版本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; } return pA; }3.2 边界情况处理在实际面试中你需要考虑这些边界情况其中一个链表为空两个链表都为空链表不相交链表相交于头节点链表相交于尾节点我们的实现已经处理了这些情况因为初始空检查处理了空链表情况不相交时最终pA和pB都会指向null退出循环相交于头节点时第一次比较就会返回3.3 时间复杂度分析每个指针最多走mn步因此时间复杂度是O(mn)。我们只用了两个指针空间复杂度是O(1)完全符合题目要求。4. 常见错误与调试技巧4.1 新手常犯的错误比较节点值而非节点本身题目要求比较节点对象而非节点值// 错误写法 if (currA.val currB.val) return currA;忘记处理不相交的情况循环可能无限进行// 危险写法 while (true) { // ... }修改了原始链表某些解法会反转链表这会改变输入4.2 调试技巧当你的解法不工作时可以画图模拟指针移动使用console.log跟踪指针位置console.log(pA: ${pA?.val}, pB: ${pB?.val});构造测试用例时确保相交节点是同一个对象const intersect new ListNode(8); const headA new ListNode(4, new ListNode(1, intersect)); const headB new ListNode(5, new ListNode(6, new ListNode(1, intersect)));5. 性能优化与变种问题5.1 提前终止优化如果已知链表长度可以先计算长度差让长链表的指针先走几步function getIntersectionNode(headA, headB) { // 计算长度 let lenA getLength(headA), lenB getLength(headB); // 对齐起点 while (lenA lenB) { headA headA.next; lenA--; } while (lenB lenA) { headB headB.next; lenB--; } // 同时前进找交点 while (headA ! headB) { headA headA.next; headB headB.next; } return headA; } function getLength(head) { let len 0; while (head) { len; head head.next; } return len; }5.2 相关变种问题判断链表是否有环Leetcode 141找出环的入口节点Leetcode 142合并两个有序链表Leetcode 21反转链表Leetcode 2066. JavaScript链表操作技巧6.1 在JavaScript中表示链表JavaScript没有内置的链表结构通常用对象模拟class ListNode { constructor(val, next null) { this.val val; this.next next; } } // 创建链表 1-2-3 const head new ListNode(1, new ListNode(2, new ListNode(3)));6.2 调试辅助函数编写一个打印链表的函数很有用function printList(head) { let current head; const result []; while (current) { result.push(current.val); current current.next; } console.log(result.join(-)); }6.3 创建相交链表的技巧在测试时需要创建真正相交的链表共享节点// 创建相交链表 const nodeC3 new ListNode(3); const nodeC2 new ListNode(2, nodeC3); const nodeC1 new ListNode(1, nodeC2); const nodeB2 new ListNode(22, nodeC2); // 在nodeC2处相交 const nodeB1 new ListNode(11, nodeB2); // 链表A1 - 2 - 3 // 链表B11 - 22 - 2 - 37. 面试实战建议7.1 面试时的解题步骤先确认理解题意询问面试官提出暴力解法并分析复杂度提出优化思路双指针编写代码并解释测试边界情况7.2 可能被问到的follow-up如果链表可能有环怎么办如果不允许修改链表结构怎么办如果内存足够大你会用什么替代方案7.3 表现加分项主动画出链表图示提前说出时间和空间复杂度主动考虑边界情况代码整洁变量命名清晰8. 扩展学习资源Leetcode链表专题包含所有链表相关问题《算法导论》链表相关理论基础《JavaScript数据结构和算法》JS实现各种数据结构VisuAlgo.net可视化算法学习网站记住掌握链表操作是成为合格开发者的基本功。这道相交链表问题看似简单但涵盖了指针操作、边界条件处理、算法优化等多个重要概念。建议你在理解这个解法后继续挑战Leetcode上其他链表问题如环形链表、反转链表等逐步构建完整的链表解题思维体系。