160. 相交链表Python详细技术解析一、题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。核心说明图示两个链表在节点c1开始相交相交节点是指内存地址相同的节点而非仅值相同题目数据保证整个链式结构中不存在环函数返回结果后链表必须保持其原始结构。自定义评测说明评测系统的输入如下程序不适用此输入仅用于创建链式结构intersectVal- 相交的起始节点的值。如果不存在相交节点这一值为 0listA- 第一个链表listB- 第二个链表skipA- 在listA中从头节点开始跳到交叉节点的节点数skipB- 在listB中从头节点开始跳到交叉节点的节点数。评测系统将根据这些输入创建链式数据结构并将两个头节点headA和headB传递给程序若能正确返回相交节点则视为正确答案。示例 1输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at 8 解释相交节点的值为 8 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。 在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。 注意值为 1 的节点是不同节点内存地址不同值为 8 的节点才是相交节点内存地址相同。示例 2输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1 输出Intersected at 2 解释相交节点的值为 2 。 从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。 在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2 输出No intersection 解释两个链表不相交返回 null 。提示listA 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 10^41 Node.val 10^50 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB]。进阶要求设计一个时间复杂度 O(m n)、仅用 O(1) 内存的解决方案。二、解题思路相交链表的核心特征若两个链表相交从相交节点开始后续所有节点完全重合内存地址相同。基于这一特征我们提供三种解法从易到难逐步优化最终满足进阶要求。2.1 核心难点区分“值相同”和“节点相同”仅值相同不代表相交必须是内存地址相同的节点保持链表原始结构不能修改链表的 next 指针也不能破坏节点顺序优化时间和空间复杂度进阶要求 O(m n) 时间、O(1) 空间需避免使用额外容器存储节点。2.2 三种解法思路解析解法1哈希集合法简单易理解空间复杂度O(m)遍历链表 A将所有节点存入哈希集合存储节点本身而非节点值遍历链表 B每遍历一个节点检查该节点是否在哈希集合中若存在直接返回该节点第一个匹配的节点即为相交起始节点若遍历完 B 仍未找到返回 null。优点思路简单代码易实现缺点使用额外哈希集合空间复杂度较高不满足进阶要求。解法2双指针法进阶解法O(1)空间O(mn)时间核心逻辑让两个指针分别遍历两个链表遍历完自身链表后切换到另一个链表的头节点继续遍历最终会在相交节点相遇若有相交。初始化两个指针pA、pB分别指向headA、headB循环遍历当pA ! pB时执行以下操作若pA不为 nullpA移动到下一个节点否则pA指向headB若pB不为 nullpB移动到下一个节点否则pB指向headA循环结束后pA或pB要么是相交节点要么是 null无相交直接返回即可。原理两个指针遍历的总长度都是m n链表A长度链表B长度若有相交会在遍历完一轮后相遇在相交节点若无相交最终都会指向 null循环终止。解法3长度对齐法进阶解法O(1)空间O(mn)时间分别计算链表 A 和链表 B 的长度lenA、lenB让较长的链表的指针先移动abs(lenA - lenB)步使两个链表的剩余长度相等同时移动两个链表的指针直到两个指针指向同一个节点相交节点或都指向 null无相交返回当前指针指向的节点。优点逻辑直观无额外空间消耗缺点需多遍历一次链表计算长度步骤略多。三、完整代码实现三种解法严格按照题目要求的链表节点定义和函数格式编写包含详细注释便于理解。解法1哈希集合法fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,x):self.valx self.nextNoneclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)-Optional[ListNode]:# 哈希集合存储链表A的所有节点node_setset()pAheadA# 遍历链表A将所有节点加入集合whilepA:node_set.add(pA)pApA.next# 遍历链表B检查节点是否在集合中pBheadBwhilepB:ifpBinnode_set:returnpB# 找到第一个相交节点直接返回pBpB.next# 无相交节点returnNone解法2双指针法推荐满足进阶要求fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,x):self.valx self.nextNoneclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)-Optional[ListNode]:# 初始化双指针分别指向两个链表的头节点pA,pBheadA,headB# 循环条件两个指针不相等whilepA!pB:# 指针A遍历完A切换到B的头节点否则继续向后pApA.nextifpAelseheadB# 指针B遍历完B切换到A的头节点否则继续向后pBpB.nextifpBelseheadA# 循环结束pA要么是相交节点要么是nullreturnpA解法3长度对齐法满足进阶要求fromtypingimportOptional# Definition for singly-linked list.classListNode:def__init__(self,x):self.valx self.nextNoneclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)-Optional[ListNode]:# 辅助函数计算链表长度defget_length(head:ListNode)-int:length0whilehead:length1headhead.nextreturnlength lenAget_length(headA)lenBget_length(headB)pA,pBheadA,headB# 让较长的链表指针先移动差值步对齐长度iflenAlenB:# A比B长pA先移动 lenA - lenB 步for_inrange(lenA-lenB):pApA.nextelse:# B比A长pB先移动 lenB - lenA 步for_inrange(lenB-lenA):pBpB.next# 同时移动两个指针寻找相交节点whilepAandpB:ifpApB:returnpA pApA.nextpBpB.next# 无相交节点returnNone四、示例验证贴合题目示例示例 1 验证双指针法链表A4 → 1 → 8 → 4 → 5lenA5链表B5 → 6 → 1 → 8 → 4 → 5lenB6pA 遍历A后切换到BpB 遍历B后切换到A总遍历长度都是 5611最终在值为8的节点相遇返回该节点与示例输出一致。示例 2 验证长度对齐法链表A1 → 9 → 1 → 2 → 4lenA5链表B3 → 2 → 4lenB3lenA - lenB 2pA 先移动2步指向1A的第三个节点同时移动pA和pB当pA指向2、pB指向2时两指针相等返回该节点与示例输出一致。示例 3 验证所有解法链表A2 → 6 → 4链表B1 → 5无相交节点哈希法遍历B后无节点在A的集合中返回null双指针法pA和pB最终都指向null循环终止返回null长度对齐法对齐后遍历两指针最终都指向null返回null与示例输出一致。五、复杂度分析解法1哈希集合法时间复杂度O(m n) → 遍历链表AO(m)和链表BO(n)哈希集合的查找操作是O(1)空间复杂度O(m) → 存储链表A的所有节点最坏情况下无相交需存储全部m个节点。解法2双指针法时间复杂度O(m n) → 两个指针最多遍历m n个节点各遍历完一个链表再遍历另一个链表的部分节点空间复杂度O(1) → 仅使用两个指针无额外空间消耗满足进阶要求。解法3长度对齐法时间复杂度O(m n) → 计算长度遍历两次链表O(m n)对齐后遍历一次O(min(m, n))总复杂度O(m n)空间复杂度O(1) → 仅使用几个变量存储长度和指针无额外空间消耗满足进阶要求。六、常见易错点与避坑指南易错点1误将“值相同”当作“节点相同” → 例如示例1中链表A的1和链表B的1值相同但不是相交节点必须判断节点本身是否相等内存地址相同而非节点值易错点2双指针法中指针切换时机错误 → 必须在指针遍历到null时才切换到另一个链表的头节点而非遍历到最后一个节点就切换易错点3长度对齐法中计算长度时遗漏节点 → 遍历链表计算长度时需循环到head为null才停止避免少算一个节点易错点4破坏链表结构 → 所有解法都不能修改节点的next指针仅移动指针遍历即可。七、总结与拓展7.1 解题核心总结相交链表的核心是“相交节点后所有节点重合”解题的关键的是找到“两个链表指针能同时到达的第一个节点”。入门推荐哈希集合法思路简单适合新手理解题目面试推荐双指针法时间和空间复杂度最优代码简洁体现算法思维备选方案长度对齐法逻辑直观适合不想记双指针切换规则的场景。7.2 同类题目拓展本题属于链表相交问题同类题目还有LeetCode 141. 环形链表 → 判断链表是否有环可结合双指针思路LeetCode 142. 环形链表 II → 找到环形链表的入环点双指针数学推导LeetCode 206. 反转链表 → 链表操作基础为复杂链表题打基础。7.3 面试注意事项面试中考察本题时通常会先让你写出哈希法再追问“如何优化空间复杂度到O(1)”此时需能快速写出双指针法并解释其原理。重点解释双指针法的逻辑两个指针遍历总长度相同若有相交则必然相遇若无相交则同时指向null无需额外空间即可找到结果。