algorithm-base 算法图解：剑指 Offer 52 与 LeetCode 160 两个链表的第一个公共节点（相交链表）双指针与哈希解法全解析

文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载本篇基于 algorithm-base 仓库中剑指Offer52两个链表的第一个公共节点一文的完整内容整理扩充而成。本文将以相交链表这一经典面试题为载体系统讲解 HashSet 存储法与双指针交替遍历法两种主流解法并给出 Java、C、JavaScript、Python、Swift、Go 六种语言的完整可运行代码帮助你理解链表按节点对象身份比较的核心语义掌握空间 O(1) 时间 O(n) 的优雅解法。题目背景与考点本题在算法题源中对应两个编号剑指 Offer 52「两个链表的第一个公共节点」与LeetCode 160「相交链表Intersection of Two Linked Lists」二者为同一道题是剑指 Offer 系列中的经典题目也是链表板块收尾阶段的必刷题。在 algorithm-base 仓库中本题被收录在两个分类之下链表篇作为链表专题的收官题目README.md 的双指针分类与 leetcode141环形链表、leetcode328奇偶链表 等共同构成双指针解题范式专题。刷本题前建议先掌握两类前置知识链表基础结构单链表由数据域与指针域组成最后一个节点指向 null。可阅读仓库中的链表详解补全概念ListNode 与 HashSet 的 APIJava 中创建节点使用new ListNode(0)HashSet 是不允许有重复元素的集合但允许 null 值、无序、非线程安全的容器其常用方法add()、contains()的具体说明见仓库的Leetcode常用类和函数。题目描述输入两个链表找出它们的第一个公共节点。例如下图所示的两条链表从某个节点开始两条链表合并为一条后续节点完全共用我们的任务就是返回这个第一个相交的节点即图中黄色节点。理解这道题的关键在于链表相交是按节点对象内存地址/引用相交而不是按节点存储的值相等。也就是说即使两个节点的val完全相同只要不是同一个节点对象就不算相交。因此下面的两种主流解法比较的都是节点引用本身而非节点值。方法一HashSet 存储法算法思路先遍历链表 A将遍历到的每一个节点对象存入 HashSet再遍历链表 B每遍历一个节点就检查其是否已存在于 HashSet 中若某个节点已存在说明它就是两条链表的第一个公共节点直接返回若遍历完链表 B 仍无命中则两条链表不相交返回 null此时tempb已走到链表末尾。public class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { ListNode tempa headA; ListNode tempb headB; //定义Hashset HashSetListNode arr new HashSetListNode(); //遍历链表A将所有值都存到arr中 while (tempa ! null) { arr.add(tempa); tempa tempa.next; } //遍历列表B如果发现某个结点已在arr中则直接返回该节点 while (tempb ! null) { if (arr.contains(tempb)) { return tempb; } tempb tempb.next; } //若上方没有返回此刻tempb为null return tempb; } }class Solution { public: ListNode * getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode * tempa headA; ListNode * tempb headB; //定义Hashset set ListNode * arr; //遍历链表A将所有值都存到arr中 while (tempa ! nullptr) { arr.insert(tempa); tempa tempa-next; } //遍历列表B如果发现某个结点已在arr中则直接返回该节点 while (tempb ! nullptr) { if (arr.find(tempb) ! arr.end()) { return tempb; } tempb tempb-next; } //若上方没有返回此刻tempb为null return tempb; } };var getIntersectionNode function (headA, headB) { let tempa headA; let tempb headB; //定义Hashset let arr new Set(); //遍历链表A将所有值都存到arr中 while (tempa) { arr.add(tempa); tempa tempa.next; } //遍历列表B如果发现某个结点已在arr中则直接返回该节点 while (tempb) { if (arr.has(tempb)) { return tempb; } tempb tempb.next; } //若上方没有返回此刻tempb为null return tempb; };class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: tempa headA tempb headB # 定义Hashset arr set() # 遍历链表A将所有值都存到arr中 while tempa is not None: arr.add(tempa) tempa tempa.next # 遍历列表B如果发现某个结点已在arr中则直接返回该节点 while tempb is not None: if tempb in arr: return tempb tempb tempb.next # 若上方没有返回此刻tempb为null return tempbclass Solution { func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) - ListNode? { var tempa headA var tempb headB var arr:SetListNode [] //遍历链表A将所有值都存到arr中 while tempa ! nil { arr.insert(tempa!) tempa tempa?.next } //遍历列表B如果发现某个结点已在arr中则直接返回该节点 while tempb ! nil { if arr.contains(tempb!) { return tempb } tempb tempb?.next } //若上方没有返回此刻tempb为null return tempb } } extension ListNode: Hashable, Equatable { public func hash(into hasher: inout Hasher) { hasher.combine(val) hasher.combine(ObjectIdentifier(self)) } public static func (lhs: ListNode, rhs: ListNode) - Bool { return lhs rhs } }实现细节说明Swift 需要额外扩展由于 Swift 的Set要求元素遵循Hashable与Equatable协议原文档的 Swift 版本通过extension ListNode补全了这两个协议其中hash(into:)混合了val与对象唯一标识ObjectIdentifier使用按引用判等——这再次印证了按节点对象比较的核心语义C 使用setListNode*存放的是指针比较的也是指针地址JavaScript/Python 天然支持对象入集Set与set()对引用类型默认按对象身份去重代码最简洁。复杂度分析指标数值说明时间复杂度O(m n)分别遍历两条链表各一次m、n 为两链表长度空间复杂度O(m)需要额外存储链表 A 的全部节点该解法思路直白、正确性显而易见代价是空间开销较大。仓库的Leetcode常用类和函数中对该容器的补充说明也适用于本题HashSet 基于 HashMap 实现不允许重复元素无序且非线程安全。方法二双指针交替遍历法最优解算法思路与方法一借助外部容器不同双指针法只需两个指针即可在 O(1) 空间内解决问题思路如下定义指针tempa从headA出发指针tempb从headB出发两个指针同步前进每次移动一步当某个指针走到链表末尾null时掉头去另一条链表的头部继续遍历因为两个指针移动速度相同、走过的总路程相同它们必然会在某个时刻指向同一个节点——这个节点就是第一个公共节点若两条链表不相交两个指针最终会同时走到 null循环退出返回 null。直观理解tempa走过的路程为链表 A 全长 链表 B 公共部分之前的长度tempb走过的路程为链表 B 全长 链表 A 公共部分之前的长度二者相等因此它们在公共区域的起点必然相遇。public class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { //定义两个节点 ListNode tempa headA; ListNode tempb headB; //循环 while (tempa ! tempb) { //如果不为空就指针下移为空就跳到另一链表的头部 tempa tempa ! null ? tempa.next: headB; tempb tempb ! null ? tempb.next: headA; } return tempa;//返回tempb也行 } }class Solution { public: ListNode * getIntersectionNode(ListNode *headA, ListNode *headB) { //定义两个节点 ListNode * tempa headA; ListNode * tempb headB; //循环 while (tempa ! tempb) { //如果不为空就指针下移为空就跳到另一链表的头部 tempa tempa ! nullptr ? tempa-next: headB; tempb tempb ! nullptr ? tempb-next: headA; } return tempa;//返回tempb也行 } };var getIntersectionNode function (headA, headB) { //定义两个节点 let tempa headA; let tempb headB; //循环 while (tempa ! tempb) { //如果不为空就指针下移为空就跳到另一链表的头部 tempa tempa ! null ? tempa.next : headB; tempb tempb ! null ? tempb.next : headA; } return tempa; //返回tempb也行 };class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: # 定义两个节点 tempa headA tempb headB # 循环 while tempa is not tempb: # 如果不为空就指针下移为空就跳到另一链表的头部 tempa tempa.next if tempa is not None else headB tempb tempb.next if tempb is not None else headA return tempa # 返回tempb也行class Solution { func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) - ListNode? { //定义两个节点 var tempa headA var tempb headB //循环 while tempa ! tempb { // 如果不为空就指针下移为空就跳到另一链表的头部 tempa tempa ! nil ? tempa?.next : headB tempb tempb ! nil ? tempb?.next : headA } return tempa //返回tempb也行 } }func getIntersectionNode(headA, headB *ListNode) *ListNode { tempA, tempB : headA, headB for tempA ! tempB { // 如果不为空就指针下移为空就跳到另一链表的头部 if tempA nil { tempA headB } else { tempA tempA.Next } if tempB nil { tempB headA } else { tempB tempB.Next } } return tempA }边界情况分析相交于链表头headA headB时循环条件一开始就不成立直接返回头节点正确不相交假设链表 A 长 m、链表 B 长 n两指针各走 m n 步后同时为 nulltempa tempb成立循环退出返回 null正确一个链表为空空链表指针立即为 null另一指针走完自身链表后也为 null返回 null正确。复杂度分析指标数值说明时间复杂度O(m n)每个指针最多走 m n 步空间复杂度O(1)仅使用两个指针无额外容器这是本题的最优解也是面试中最受青睐的写法思想巧妙但代码极短六种语言的核心逻辑均只有三五行。与快慢指针的关联本题的双指针属于相遇型双指针与仓库中另一道经典题leetcode141环形链表快慢指针判断环同属双指针范式环形链表利用速度差追及本题利用路程对齐相交二者共同点是通过指针的相对运动消除链表长度差异带来的干扰。方法三拓展长度差法原文档的贡献者 jaredliw 补充了另外两种值得一试的解法此处完整保留并展开说明。思路先分别遍历两条链表统计长度。设较长链表比短链表长 k 个节点则让较长链表的指针先走 k 步之后两个指针再同步前进。由于此时两个指针距离公共节点的剩余路程一致它们必然同时到达第一个公共节点。原理链表相交后公共部分对两条链表是完全共享的因此两链表尾部对齐后公共节点到链表末尾的距离相等。长度差法通过先走 k 步显式完成对齐与双指针法的掉头隐式对齐殊途同归。方法四拓展成环法思路将其中一条链表的头尾相连把链表 A 的尾节点 next 指向链表 A 的头节点形成环此时问题转化为在一条带环链表中寻找环的入口节点——而这个环的入口恰好就是两链表的第一个公共节点。直接套用仓库中leetcode142环形链表2讲解的快慢指针找环入口算法即可求解。注意该解法会修改原链表结构实际工程使用后需要恢复链表否则会破坏输入数据但它把相交问题统一到了成环问题的解题框架下从模型归约的角度看非常巧妙正如贡献者所说拍腿叫好。四种解法对比总结方法时间复杂度空间复杂度是否修改链表特点HashSet 存储法O(m n)O(m)否思路最直观适合快速 AC双指针交替遍历法O(m n)O(1)否最优解代码极简面试首选长度差法O(m n)O(1)否显式对齐长度易于推导证明成环法O(m n)O(1)是需恢复模型归约巧妙与环形链表题打通仓库内延伸阅读剑指Offer52两个链表的第一个公共节点本文原文档链表详解链表基础概念与类型Leetcode常用类和函数ListNode、HashSet、Set 的 API 速查leetcode141环形链表快慢指针判断环leetcode142环形链表2快慢指针找环入口成环法前置知识README.md查看链表篇与双指针专题的完整题目索引小结本题作为链表板块的收官题核心考点在于节点按引用比较的语义理解以及用双指针把空间复杂度降到 O(1) 的经典技巧。掌握 HashSet 法保证正确性吃透双指针法赢得复杂度优势再辅以长度差法与成环法的思路拓展即可从容应对面试中的变体提问。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐LeetCode-Book 剑指 Offer 52 详解双指针对齐法求两个链表的第一个公共节点LeetCode Book 剑指 Offer 52 详解双指针对齐法求两个链表的第一个公共节点 本篇基于 LeetCode Book 仓库中《剑指 Offer示例工程CS-Notes 剑指 Offer 题解 52用 O(1) 空间的双指针法求两个链表的第一个公共结点CS Notes 剑指 Offer 题解 52用 O 1 空间的双指针法求两个链表的第一个公共结点 本篇基于 CS Notes 仓库中剑指 Offer 题解的知识库文档教程LeetCode 160. 相交链表Intersection of Two Linked Lists题解哈希法与双指针法详解LeetCode 160. 相交链表Intersection of Two Linked Lists题解哈希法与双指针法详解 导读 本文基于开源仓库 le文档教程知识库上一篇uBlock Origin终极指南3步打造纯净无广告的浏览体验下一篇Torrentio Scraper如何打造你的专属影视资源聚合引擎创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考