我要评论已解答
给你两个单链表的头节点 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，因为在链表 a 和链表 b 之中值为 1 的节点 (a 中第二个节点和 b 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 a 和链表 b 中值为 8 的节点 (a 中第三个节点，b 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectval = 2, lista = [1,9,1,2,4], listb = [3,2,4], skipa = 3, skipb = 1
输出：intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 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
输出：null
解释：从各自的表头开始算起，链表 a 为 [2,6,4]，链表 b 为 [1,5]。
由于这两个链表不相交，所以 intersectval 必须为 0，而 skipa 和 skipb 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
lista中节点数目为mlistb中节点数目为n1 <= m, n <= 3 * 1041 <= node.val <= 1050 <= skipa <= m0 <= skipb <= n- 如果
lista和listb没有交点，intersectval为0 - 如果
lista和listb有交点，intersectval == lista[skipa] == listb[skipb]
进阶：你能否设计一个时间复杂度 o(m + n) 、仅用 o(1) 内存的解决方案？
class solution:
def getintersectionnode(self, heada: listnode, headb: listnode) -> optional[listnode]:
if not heada or not headb:
return none
pa, pb = heada, headb
while pa != pb:
pa = pa.next if pa else headb
pb = pb.next if pb else heada
return pa
下面是对代码的逐行解释：
python
复制
class solution:
定义一个名为 solution 的类，其中包含求解相交链表问题的方法。
python
复制
def getintersectionnode(self, heada: listnode, headb: listnode) -> optional[listnode]:
定义一个名为 getintersectionnode 的方法，接受两个参数 heada 和 headb，它们分别是链表 a 和链表 b 的头节点。返回值类型是 optional[listnode]，表示返回的可能是一个 listnode 或 none。
python
复制
if not heada or not headb:
return none
检查链表 a 或链表 b 是否为空。如果任意一个链表为空，则不可能有相交节点，直接返回 none。
python
复制
pa, pb = heada, headb
初始化两个指针 pa 和 pb，分别指向链表 a 和链表 b 的头节点。
python
复制
while pa != pb:
进入一个 while 循环，持续执行直到 pa 和 pb 指向同一个节点（即相交节点）或都为 none（即没有相交节点）。
python
复制
pa = pa.next if pa else headb
更新指针 pa 的位置。如果 pa 当前不是 none，则移到下一个节点；如果 pa 当前是 none，则将其重定位到链表 b 的头节点。
python
复制
pb = pb.next if pb else heada
更新指针 pb 的位置。如果 pb 当前不是 none，则移到下一个节点；如果 pb 当前是 none，则将其重定位到链表 a 的头节点。
python
复制
return pa
当 pa 和 pb 相等（即指向同一个节点）时，退出循环并返回 pa。此时，pa 和 pb 要么指向相交节点，要么都为 none（表示没有相交节点）。
详细解释
-
初始化与检查：
if not heada or not headb:：首先检查输入的两个链表是否为空。如果其中任何一个为空，则不可能存在相交节点，直接返回none。
-
双指针初始化：
pa, pb = heada, headb：初始化两个指针pa和pb，分别指向链表 a 和链表 b 的头节点。
-
指针遍历：
while pa != pb:：进入循环，直到两个指针指向同一个节点（即相交节点）或都为none。pa = pa.next if pa else headb：如果pa不是none，则指向下一个节点；如果是none，则重定位到链表 b 的头节点。pb = pb.next if pb else heada：如果pb不是none，则指向下一个节点；如果是none，则重定位到链表 a 的头节点。
-
返回结果：
return pa：当pa和pb相等时（即指向相同节点或都为none），返回pa，即相交节点或none。
通过这种方式，即使链表的长度不同，两个指针也会同时遍历到相交节点或者链表的末尾，从而正确地找到相交节点或确认没有相交。
发表评论