LeetCode-Book 图解 LCR 171 训练计划 V：双指针求解两链表相交节点（含 Python / Java / C++ 实现）-开发者社区

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）时切换到另一条链表的头节点继续遍历。

Python

class 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 A

Java

public 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; } }

C++

class 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 headB，Java 用三元表达式A != null ? A.next : headB，C++ 用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_interview）：
- Python 版本：selected_coding_interview/codes/python/lc_160_intersection_of_two_linked_lists.py，并附有驱动测试：构造[4, 1, 8, 4, 5]与[5, 6, 1, 8, 4, 5]两条链表，其中公共节点值为8；
- Java 版本：selected_coding_interview/codes/java/lc_160_intersection_of_two_linked_lists/lc_160_intersection_of_two_linked_lists.java，main中使用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 52（sword_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，程序会打印相交节点的值（示例用例中为8）；
Java：运行 selected_coding_interview/codes/java/lc_160_intersection_of_two_linked_lists/lc_160_intersection_of_two_linked_lists.java 中的main方法，输出Intersection node value: 8；
C++：selected_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）等使用双指针技巧的同类题目中，做到举一反三。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考