相交链表
Intersection of Two Linked Lists
本机进度仅保存在当前浏览器
题目描述
给你两个单链表的头节点 headA 与 headB，请你找出并返回两个单链表相交的起始节点；若不相交返回 null。整个链式结构中不存在环。要求 O(n) 时间、O(1) 空间。
示例：两链表在值为 8 的节点相交。
解题思路
- 两链表长度不同，直接同步走无法对齐；核心是消除长度差。
- 指针 p 从 A 出发、q 从 B 出发，各自走到底后跳到另一条链表的头继续走。
- 这样两者走过的总长度同为 la + lb，长度差被"换轨"抵消；若相交必然在交点相遇，不相交则同时到达 null。
- 也可以先算长度差让长链先走差值步，本质相同。
参考实现
查看参考实现Python · 建议先自行作答
def getIntersectionNode(headA, headB):
# 双指针换轨：走完自己的路再走对方的路，等距消除长度差
p, q = headA, headB
while p is not q:
p = p.next if p else headB
q = q.next if q else headA
return p