网硕互联帮助中心160. 相交链表
算法思路
核心思想：
- 使用两个指针 pA 和 pB，分别从 headA 和 headB 开始遍历。
- 当 pA 遍历到链表 A 的末尾时，跳转到链表 B 的头节点；当 pB 遍历到链表 B 的末尾时，跳转到链表 A 的头节点。
- 如果两个链表相交，pA 和 pB 最终会在相交节点相遇；如果不相交，pA 和 pB 会同时到达 None。
具体步骤：
- 初始化 pA = headA，pB = headB。
- 当 pA != pB 时：
- 如果 pA 为空，跳转到 headB；否则继续遍历 pA.next。
- 如果 pB 为空，跳转到 headA；否则继续遍历 pB.next。
- 返回 pA（即相交节点）。
关键点：
- 通过跳转指针的方式，确保两个指针遍历的总长度相同。
- 时间复杂度为 O(m + n)，空间复杂度为 O(1)。
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA, headB):
if not headA or not headB:
return None
pA, pB = headA, headB
while pA != pB:
pA = headB if not pA else pA.next
pB = headA if not pB else pB.next
return pA
题解里看到的图解，很清晰
评论前必须登录！
注册