企业官网建设流程全解析

• 文档
• 教程
• 知识库

本篇基于 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奇偶链表 等共同构成双指针解题范式专题。

刷本题前建议先掌握两类前置知识：

1. 链表基础结构：单链表由数据域与指针域组成，最后一个节点指向 null。可阅读仓库中的链表详解补全概念；
2. ListNode 与 HashSet 的 API：Java 中创建节点使用new ListNode(0)，HashSet 是"不允许有重复元素的集合但允许 null 值、无序、非线程安全"的容器，其常用方法add()、contains()的具体说明见仓库的Leetcode常用类和函数。

题目描述

输入两个链表，找出它们的第一个公共节点。

例如下图所示的两条链表，从某个节点开始两条链表"合并"为一条，后续节点完全共用，我们的任务就是返回这个第一个相交的节点（即图中黄色节点）。

理解这道题的关键在于：链表相交是按"节点对象"（内存地址/引用）相交，而不是按节点存储的值相等。也就是说，即使两个节点的val完全相同，只要不是同一个节点对象，就不算相交。因此下面的两种主流解法比较的都是节点引用本身，而非节点值。

方法一：HashSet 存储法

算法思路

1. 先遍历链表 A，将遍历到的每一个节点对象存入 HashSet；
2. 再遍历链表 B，每遍历一个节点就检查其是否已存在于 HashSet 中；
3. 若某个节点已存在，说明它就是两条链表的第一个公共节点，直接返回；
4. 若遍历完链表 B 仍无命中，则两条链表不相交，返回 null（此时tempb已走到链表末尾）。

public class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { ListNode tempa = headA; ListNode tempb = headB; //定义Hashset HashSet<ListNode> arr = new HashSet<ListNode>(); //遍历链表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 tempb

class Solution { func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? { var tempa = headA var tempb = headB var arr:Set<ListNode> = [] //遍历链表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++ 使用set<ListNode*>：存放的是指针，比较的也是指针地址；
• JavaScript/Python 天然支持对象入集：Set与set()对引用类型默认按对象身份去重，代码最简洁。

复杂度分析

该解法思路直白、正确性显而易见，代价是空间开销较大。仓库的Leetcode常用类和函数中对该容器的补充说明也适用于本题：HashSet 基于 HashMap 实现，不允许重复元素，无序且非线程安全。

方法二：双指针交替遍历法（最优解）

算法思路

与方法一"借助外部容器"不同，双指针法只需两个指针即可在 O(1) 空间内解决问题，思路如下：

1. 定义指针tempa从headA出发，指针tempb从headB出发；
2. 两个指针同步前进，每次移动一步；
3. 当某个指针走到链表末尾（null）时，掉头去另一条链表的头部继续遍历；
4. 因为两个指针移动速度相同、走过的总路程相同，它们必然会在某个时刻指向同一个节点——这个节点就是第一个公共节点；
5. 若两条链表不相交，两个指针最终会同时走到 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 步后同时为 null，tempa == tempb成立，循环退出返回 null，正确；
• 一个链表为空：空链表指针立即为 null，另一指针走完自身链表后也为 null，返回 null，正确。

复杂度分析

这是本题的最优解，也是面试中最受青睐的写法：思想巧妙但代码极短，六种语言的核心逻辑均只有三五行。

与快慢指针的关联

本题的双指针属于"相遇型双指针"，与仓库中另一道经典题leetcode141环形链表（快慢指针判断环）同属双指针范式：环形链表利用"速度差"追及，本题利用"路程对齐"相交，二者共同点是通过指针的相对运动消除链表长度差异带来的干扰。

方法三（拓展）：长度差法

原文档的贡献者 jaredliw 补充了另外两种值得一试的解法，此处完整保留并展开说明。

思路：先分别遍历两条链表统计长度。设较长链表比短链表长 k 个节点，则让较长链表的指针先走 k 步；之后两个指针再同步前进。由于此时两个指针距离公共节点的"剩余路程"一致，它们必然同时到达第一个公共节点。

原理：链表相交后，公共部分对两条链表是完全共享的，因此两链表"尾部对齐"后，公共节点到链表末尾的距离相等。长度差法通过"先走 k 步"显式完成对齐，与双指针法的"掉头"隐式对齐殊途同归。

方法四（拓展）：成环法

思路：将其中一条链表的头尾相连（把链表 A 的尾节点 next 指向链表 A 的头节点，形成环），此时问题转化为"在一条带环链表中寻找环的入口节点"——而这个环的入口恰好就是两链表的第一个公共节点。直接套用仓库中leetcode142环形链表2讲解的"快慢指针找环入口"算法即可求解。

注意：该解法会修改原链表结构，实际工程使用后需要恢复链表，否则会破坏输入数据；但它把"相交问题"统一到了"成环问题"的解题框架下，从模型归约的角度看非常巧妙，正如贡献者所说"拍腿叫好"。

四种解法对比总结

仓库内延伸阅读

• 剑指Offer52两个链表的第一个公共节点（本文原文档）
• 链表详解（链表基础概念与类型）
• Leetcode常用类和函数（ListNode、HashSet、Set 的 API 速查）
• leetcode141环形链表（快慢指针判断环）
• leetcode142环形链表2（快慢指针找环入口，成环法前置知识）
• README.md（查看链表篇与双指针专题的完整题目索引）

小结：本题作为链表板块的收官题，核心考点在于"节点按引用比较"的语义理解，以及用双指针把空间复杂度降到 O(1) 的经典技巧。掌握 HashSet 法保证正确性，吃透双指针法赢得复杂度优势，再辅以长度差法与成环法的思路拓展，即可从容应对面试中的变体提问。

• 文档
• 教程
• 知识库