LeetCode-Book 图解 LCR 171 训练计划 V双指针求解两链表相交节点含 Python / Java / C 实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读「LCR 171. 训练计划 V」的本质是两个链表的第一个公共节点问题给定两个单链表的头节点headA与headB需要找出并返回两个链表相交的起始节点。本文以 LeetCode-Book 仓库中 leetbook_ioa/docs/LCR 171. 训练计划 V.md 为主体完整推导双指针交替遍历解法的数学原理给出 Python、Java、C 三种语言的直接可用代码并结合仓库内lc_160_intersection_of_two_linked_lists系列源码与 剑指 Offer 52. 两个链表的第一个公共节点 的对应实现进行交叉验证帮助读者彻底掌握这类链表相交检测题目的最优解法与复杂度分析。一、题目回顾与问题模型「训练计划 V」对应 LeetCode 第 160 题Intersection of Two Linked Lists与《剑指 Offer》第 52 题是同一道题。题目给出两个单向链表的头节点要求返回两个链表相交的起始节点若两个链表不相交则返回null。在分析前先约定符号沿用原文档记号node两个链表的第一个公共节点a链表headA的节点总数b链表headB的节点总数c两链表公共尾部从node到链表末尾的节点数量。由此可以得到两条关键信息头节点headA到node之前共有 $a - c$ 个节点头节点headB到node之前共有 $b - c$ 个节点。链表相交在这里的含义是从某个节点开始两条链表共享同一段节点公共尾部。由于单链表每个节点只有一个next指针两个链表一旦相交相交点之后的所有节点必然完全相同形成 Y 字形结构。二、双指针解法让两个指针走完自己再走对方朴素思路是使用哈希表记录链表 A 的所有节点再遍历链表 B 判断是否有节点出现过。这样时间复杂度为 $O(a b)$但空间复杂度为 $O(a)$。而本题追求 $O(1)$ 空间于是采用双指针交替遍历的思路。构建两个节点指针A、B分别指向链表头节点headA、headB然后执行如下操作指针A先遍历完链表headA再开始遍历链表headB当它走到公共节点node时共走的步数为$$ a (b - c) $$指针B先遍历完链表headB再开始遍历链表headA当它走到公共节点node时共走的步数为$$ b (a - c) $$由于$$ a (b - c) b (a - c) $$两个指针必然会在同一时刻重合重合时分为两种情况两链表有公共尾部$c 0$指针A、B同时指向「第一个公共节点」node两链表无公共尾部$c 0$指针A、B同时指向null各自遍历完 $a b$ 个节点后同时走到链表末尾的空指针。因此循环结束后直接返回指针A即可。直观理解两条链表的长度差被走完自己再走对方的操作抹平了——每个指针都恰好走完a b个节点其中独有部分走一次、公共部分走两次最终同时到达相遇点或末尾null。三、代码实现Python / Java / C原文档给出了三种语言的官方解法实现均可直接复制运行。核心循环条件为while (A ! B)指针走到链表末尾null时切换到另一条链表的头节点继续遍历。Pythonclass Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: A, B headA, headB while A ! B: A A.next if A else headB B B.next if B else headA return AJavapublic class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode A headA, B headB; while (A ! B) { A A ! null ? A.next : headB; B B ! null ? B.next : headA; } return A; } }Cclass Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *A headA, *B headB; while (A ! B) { A A ! nullptr ? A-next : headB; B B ! nullptr ? B-next : headA; } return A; } };三种语言的核心逻辑完全一致仅指针判空写法不同Python 用A else headBJava 用三元表达式A ! null ? A.next : headBC 用A ! nullptr ? A-next : headB。需要注意切换头节点发生在指针为null的那一步当指针走完自己所在链表后下一步指向另一条链表的头节点从而完成拼接遍历。四、复杂度分析时间复杂度 $O(a b)$最差情况下即 $|a - b| 1$、$c 0$两链表长度接近且不相交两个指针需要各自遍历完两条链表共访问 $a b$ 个节点空间复杂度 $O(1)$节点指针A、B只使用常数大小的额外空间不借助哈希表或数组。这也是本题相对哈希表 集合方案空间 $O(a)$的核心优势在不使用额外存储的前提下仍保持线性时间。五、仓库源码佐证同一解法在三套代码库中的落地LeetCode-Book 仓库中该题的解法在多个子项目中都有对应源码且算法实现与原文档完全一致可作为交叉验证依据笔面试精选 88 题selected_coding_interviewPython 版本selected_coding_interview/codes/python/lc_160_intersection_of_two_linked_lists.py并附有驱动测试构造[4, 1, 8, 4, 5]与[5, 6, 1, 8, 4, 5]两条链表其中公共节点值为8Java 版本selected_coding_interview/codes/java/lc_160_intersection_of_two_linked_lists/lc_160_intersection_of_two_linked_lists.javamain中使用ListNode.arrToLinkedList构造相同用例C 版本selected_coding_interview/codes/cpp/lc_160_intersection_of_two_linked_lists/lc_160_intersection_of_two_linked_lists_s1.cpp。剑指 Offer 52sword_for_offer原文档 sword_for_offer/docs/剑指 Offer 52. 两个链表的第一个公共节点.md 给出完全相同的推导与三语言代码印证该解法是官方与社区通用的标准答案。从源码结构可以推断各语言的 ListNode 定义统一封装在 include 公共模块中例如 Python 的 selected_coding_interview/codes/python/include/linked_list.py 提供ListNode类以及list_to_linked_list/linked_list_to_list/get_list_node等链表构造与序列化工具函数方便读者本地构造测试用例并验证算法正确性。六、如何本地运行与验证仓库代码采用解法代码 驱动代码的组织方式读者无需提交到在线评测平台即可本地验证Python直接运行 selected_coding_interview/codes/python/lc_160_intersection_of_two_linked_lists.py程序会打印相交节点的值示例用例中为8Java运行 selected_coding_interview/codes/java/lc_160_intersection_of_two_linked_lists/lc_160_intersection_of_two_linked_lists.java 中的main方法输出Intersection node value: 8Cselected_coding_interview/codes/cpp/lc_160_intersection_of_two_linked_lists/lc_160_intersection_of_two_linked_lists_s1.cpp 预留了测试用例入口// TODO: Add specific test case可自行补充两条链表并调用getIntersectionNode验证。注意上述驱动用例构造的两条链表共享节点8, 4, 5属于有公共尾部$c 0$场景读者也可自行构造完全不相交的两条链表验证返回值为null的情况。七、小结「训练计划 V / 两个链表的第一个公共节点」是链表类面试题中双指针消除长度差思想的经典代表。通过让两个指针分别遍历完自己所在链表后再转向对方链表将两条链表的长度差转化为相同步数内的汇合最终以 $O(a b)$ 时间、$O(1)$ 空间优雅地完成相交检测。掌握这一思路后可以顺带迁移到环形链表、链表倒数第 k 个节点LCR 140. 训练计划 II等使用双指针技巧的同类题目中做到举一反三。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考