LeetCode 160 相交链表Intersection of Two Linked Lists四种解法从暴力到最优双指针全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 articles/intersection-of-two-linked-lists.md 为骨架系统讲解 LeetCode 160「相交链表」的四种经典解法暴力枚举、哈希集合、长度对齐双指针与跳跃式双指针。文中所有代码与复杂度结论均可在本仓库的 python/0160-intersection-of-two-linked-lists.py、cpp/0160-intersection-of-two-linked-lists.cpp、java/0160-intersection-of-two-linked-lists.java 等多语言实现中找到对应证据。读完你将掌握链表按引用而非按值判等的核心思想并能从 O(m×n) 暴力解一路优化到 O(mn) 时间、O(1) 空间的最优解。问题定义与前置知识题目给定两个单链表的头节点headA与headB要求返回两个链表相交的起始节点若不相交则返回null。这里的「相交」有严格定义两个链表从某个节点起共享同一个节点对象内存引用相同而不是仅仅拥有相等的节点值。在动手解题前需要具备以下基础能力链表遍历能够遍历单向链表并理解「节点引用」与「节点值」的区别——这是本题最大的陷阱来源哈希集合使用集合在 O(1) 时间内完成节点引用的存储与查找如 Python 的set、Java 的HashSet双指针同时操纵两个指针遍历链表结构链表长度计算通过一次完整遍历统计链表长度。解法一暴力枚举Brute Force直觉最直接的想法是遍历第一条链表的每一个节点对每个节点再完整遍历第二条链表判断是否存在同一个对象。由于相交意味着两个链表共享真实的节点引用而非仅仅值相等的节点所以这里必须做引用比较。算法步骤从headA开始遍历第一条链表对第一条链表的每个节点完整遍历第二条链表若第二条链表中存在某个节点与当前第一条链表节点按引用相等立即返回该节点全部检查完毕仍未命中返回null。代码实现Python 主实现# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]: while headA: cur headB while cur: if headA cur: # 按引用比较而非 headA.val cur.val return headA cur cur.next headA headA.next return None原文档中该解法还提供了 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 共 8 种语言的等价实现核心逻辑完全一致外层循环驱动headA内层循环用临时指针cur扫过整条链表 B命中即返回。复杂度分析时间复杂度$O(m \times n)$其中 $m$ 是第一条链表长度$n$ 是第二条链表长度。最坏情况不相交或交点在尾部下外层每个节点都要扫描完整条第二条链表空间复杂度$O(1)$ 额外空间仅使用了若干指针变量。暴力解正确但低效仅适用于链表规模极小的场景下面逐步优化。解法二哈希集合Hash Set直觉暴力解的内层扫描是在重复做「查找」工作。改用哈希集合后查找从 O(n) 降为平均 O(1)先把第一条链表的所有节点引用存入集合再遍历第二条链表第一个命中集合的节点就是交点。算法步骤遍历第一条链表将所有节点引用加入哈希集合遍历第二条链表对第二条链表的每个节点检查其是否已存在于集合中返回第一个匹配到的节点若遍历完仍未命中返回null。代码实现Python 主实现# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]: nodeSet set() cur headA while cur: nodeSet.add(cur) # 存引用Python 的 ListNode 默认按 id 哈希 cur cur.next cur headB while cur: if cur in nodeSet: # 按引用查重 return cur cur cur.next return None各语言实现要点对应原文档的 8 种语言版本Java / C#使用HashSetListNode/HashSetListNodeListNode的默认equals/hashCode即基于引用Cunordered_setListNode*以指针为键Gomap[*ListNode]bool以指针为键KotlinmutableSetOfListNode()SwiftSetObjectIdentifier显式用ObjectIdentifier(cur!)包装节点对象标识RustHashSet中存入node.as_ref() as *const ListNode原始指针因为OptionBoxListNode具有唯一所有权必须通过指针身份比较。复杂度分析时间复杂度$O(m n)$两次线性遍历空间复杂度$O(m)$用于存储第一条链表的所有节点引用。哈希解在时间上达到最优但引入了与第一条链表长度成正比的额外空间。能否做到 O(1) 空间双指针解法给出了答案。解法三双指针 I —— 长度对齐法直觉如果两条链表相交那么交点之后的部分完全相同。因此交点到链表尾部的距离是固定的交点距离链表末尾的距离对两条链表而言必然相等。既然如此只要让两个指针从「距离末尾相同距离」的位置同时出发就能同步走到交点。做法是先分别算出两条链表长度把较长链表的指针先前进|m - n|步完成对齐。算法步骤分别计算两条链表的长度m与n找出较长链表将其指针提前前进|m - n|个节点两个指针同步逐节点前进当两个指针指向同一节点时返回该节点若同时走到null说明不相交返回null。代码实现Python 主实现# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]: def getLength(head): length, cur 0, head while cur: length 1 cur cur.next return length m getLength(headA) n getLength(headB) l1, l2 headA, headB if m n: # 保证 l1 指向较长链表 m, n n, m l1, l2 headB, headA while m - n: # 较长链表指针前进长度差 m - 1 l1 l1.next while l1 ! l2: # 同步前进直到相遇或同时为 null l1 l1.next l2 l2.next return l1原文档中该解法同样给出了 Java辅助函数getLength 交换l1/l2、Cswap(m, n)、JavaScript、C#、Go、Kotlinrepeat(m - n)、Swiftswap(m, n)与 Rust 的实现。需要特别注意的是 Rust 版本受OptionBoxListNode唯一所有权约束比较时使用std::ptr::eq进行原始指针身份判断。复杂度分析时间复杂度$O(m n)$两次长度计算各 O(m)/O(n)对齐与同步前进合计不超过 O(m n)空间复杂度$O(1)$ 额外空间只用了常数个指针变量。解法四双指针 II —— 跳跃式双指针最优解直觉更巧妙的做法是完全不计算长度。两个指针分别从headA、headB出发任一指针走到链表末尾null时立即跳转到另一条链表的头节点继续前进。经过至多m n步两个指针走过的总路程必然相等。若存在交点它们会在交点处相遇若不存在交点它们会同时到达null并相等退出循环。为什么正确设交点前 A 段长度为a、B 段长度为b、共享段长度为c。指针 1 走a c b指针 2 走b c a两者总路程相同因此在共享段起点交点必然首次相遇。若不相交两个指针各走m n步后同时到达nullnull null使循环自然终止。算法步骤初始化l1 headAl2 headB当l1 ! l2时循环若l1为null将l1重置为headB否则前进到l1.next若l2为null将l2重置为headA否则前进到l2.next循环结束时l1 l2直接返回l1交点节点或null。代码实现Python 主实现# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]: l1, l2 headA, headB while l1 ! l2: l1 l1.next if l1 else headB l2 l2.next if l2 else headA return l1这个解法简短到极致却同时保证了正确性、$O(mn)$ 时间与 $O(1)$ 空间。仓库源码印证最优解的多语言落地本仓库各语言目录下以0160-编号保存了本题的实现它们统一采用解法四的跳跃式双指针策略与本文档结论完全一致python/0160-intersection-of-two-linked-lists.pywhile l1 ! l2: l1 l1.next if l1 else headB; l2 l2.next if l2 else headAcpp/0160-intersection-of-two-linked-lists.cpp使用(trevA ! NULL) ? trevA-next : headB三目运算完成指针重定向java/0160-intersection-of-two-linked-lists.javaa (a ! null) ? a.next : headBgo/0160-intersection-of-two-linked-lists.go用if a nil { a headB } else { a a.Next }显式分支kotlin/0160-intersection-of-two-linked-lists.kta if(a ! null) a.next else headBjavascript/0160-intersection-of-two-linked-lists.jsa a null ? headB : a.nextc/0160-intersection-of-two-linked-lists.c在循环内部完成「先判等再重定向」if (currA currB) return currA;并在指针走到NULL时分别重置为另一链表头逻辑上等价于跳跃式双指针。可见无论语言生态如何差异GC 引用 vs 裸指针、nilvsnullvsNULL解法四的核心思想保持一致两个指针互换起点用总路程相等消除长度差。此外原文档还给出了 Swift 与 Rust 版本其中 Rust 因OptionBoxListNode的唯一所有权限制采用先转成Vec*const ListNode再自尾向首比对指针的方式实现可作为理解 Rust 所有权模型下链表题处理方式的参考。复杂度分析时间复杂度$O(m n)$每个指针至多完整遍历两条链表各一次空间复杂度$O(1)$ 额外空间。常见陷阱Common Pitfalls陷阱一按节点值比较而不是按引用比较相交意味着两个链表共享同一个节点对象而非拥有值相等的节点。若错误地使用nodeA.val nodeB.val判断会在两条链表存在相同值节点时产生误报false positive。必须直接比较节点引用Python 的、Java/C/Go/C# 的、JavaScript 的、Kotlin/Swift 的以及 Rust 中的std::ptr::eq。陷阱二未正确处理不相交链表当两条链表不相交时跳跃式双指针会在两个指针同时变为null时自然终止——因为循环条件l1 ! l2在null null时不成立。但某些实现若漏掉「指针走到末尾应跳转到另一链表头」的重定向逻辑就会陷入死循环。务必保证循环条件包含指针相等判断并涵盖null的情况重定向必须在指针为null时发生且每个指针至多跳转一次跳转超过一次会导致错误。四种解法对比总结解法核心思路时间复杂度空间复杂度适用场景暴力枚举双重循环按引用两两比对$O(m \times n)$$O(1)$链表极短、仅作教学理解哈希集合存 A 链引用、扫 B 链查重$O(m n)$$O(m)$允许 O(m) 额外空间、追求书写简单双指针 I长度对齐后同步前进$O(m n)$$O(1)$需要 O(1) 空间、思路直观双指针 II指针互换起点总路程相等$O(m n)$$O(1)$面试与竞赛标准答案其中 $m$ 为第一条链表长度$n$ 为第二条链表长度。四种解法从易到难完整覆盖了「暴力 → 空间换时间 → 长度对齐 → 巧妙双指针」的优化路径是理解链表引用语义与双指针技巧的经典教材级题目也是本仓库链表专题如 reverse-a-linked-list.md、linked-list-cycle-detection.md中反复出现的核心思想。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考