LeetCode hot100——相交链表

相交链表160. 相交链表 - 力扣LeetCode1. 生活化类比两个人的“相遇之路”想象两个人在不同的起点出发准备去往同一个终点。路径 A 比较短路径 B 比较长。只要两人一直往前走因为速度一样但路程不等他们到达终点的时间肯定不同也就很难在途中“并肩而行”。浪漫的逻辑如果我走完我的路再去走你走过的路而你走完你的路再去走我走过的路。那么我们两人走过的总路程就完全相等了路程 A 路程 B 路程 B 路程 A。在这个过程中如果我们有重合的部分相交点我们一定会在第二段路程中同时到达那个点。2. 核心思路换道行驶这道题的难点在于两个链表的长度不一直接遍历很难对齐。第一步双指针出发。准备两个指针pa和pb分别指向两个链表的头。第二步走到尽头就“换道”。当pa走到链表 A 的末尾时把它重定向到链表 B 的头部。当pb走到链表 B 的末尾时把它重定向到链表 A 的头部。第三步终将相遇。如果两个链表相交它们会在交点处相等pa pb。如果两个链表不相交它们最终会同时指向null从而跳出循环。3. 代码实现function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null { // 1. 边界处理 if (headA null || headB null) return null; let pa: ListNode | null headA; let pb: ListNode | null headB; // 2. 核心逻辑你走过我走的路我走过你走的路 while (pa ! pb) { // 如果走到头了就换到另一条路继续走 pa (pa null) ? headB : pa.next; pb (pb null) ? headA : pb.next; } // 3. 返回相交节点或 null return pa; }4. 复杂度分析时间复杂度$O(m n)$。每个指针最多遍历两个链表各一次。空间复杂度$O(1)$。只使用了两个常数级别的指针变量。5. ACM 模式写法主函数和调用手动构建相交结构function main() { try { // 1. 创建公共相交部分 const intersectVal new ListNode(8); intersectVal.next new ListNode(4); intersectVal.next.next new ListNode(5); // 2. 创建链表 A: 4 - 1 - [8 - 4 - 5] const headA new ListNode(4); headA.next new ListNode(1); headA.next.next intersectVal; // 3. 创建链表 B: 5 - 6 - 1 - [8 - 4 - 5] const headB new ListNode(5); headB.next new ListNode(6); headB.next.next new ListNode(1); headB.next.next.next intersectVal; // 4. 调用算法并打印 const result getIntersectionNode(headA, headB); console.log(result ? result.val : No Intersection); } catch (err) { console.log(err); } } main();疑问分析1. 为什么最后会同时指向null如果链表 A 长度为 $L1$链表 B 长度为 $L2$。不相交时两人都走了 $L1 L2$ 步。此时pa走完了 A 再走完了 B停在末尾的nullpb走完了 B 再走完了 A也停在null。null null成立循环结束。2. 这种解法比“先算长度差”好在哪里算长度差需要写好几个while循环算 A 长、算 B 长、移动长链表指针代码冗长。而“换道法”利用了数学上的对等性代码极度优雅且不容易写错。