链表相交

难度: Easy

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,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 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 10⁴
1 <= Node.val <= 10⁵
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

Submission

运行时间: 168 ms

内存: 29.6 MB

# 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) -> ListNode:
        p = headA
        q = headB
        while p != q:
            p = p.next if p else headB
            q = q.next if q else headA
        return p

Explain

这个解法利用了两个指针p和q分别遍历两个链表headA和headB。初始时，p指向headA的头节点，q指向headB的头节点。当p和q不相等时，继续遍历。如果p到达链表A的尾部，则将p重新指向链表B的头节点；同理，如果q到达链表B的尾部，则将q重新指向链表A的头节点。这样调整后，p和q继续前进，直到它们相遇或都变为null。如果它们相遇，则返回相遇的节点，这就是两链表的交点。如果p和q都变为null，说明两个链表不相交，返回null。

时间复杂度: O(m+n)

空间复杂度: O(1)

# 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) -> ListNode:
        p = headA  # 初始化指针p指向链表A的头节点
        q = headB  # 初始化指针q指向链表B的头节点
        while p != q:  # 当p和q不相遇时循环
            p = p.next if p else headB  # 若p已到链表末端，则跳到链表B的头节点
            q = q.next if q else headA  # 若q已到链表末端，则跳到链表A的头节点
        return p  # 返回相交的节点，若无交点则为null

Explore

当p或q到达链表末端时，将它们指向另一个链表的头节点，这样做是为了消除两个链表长度不同带来的影响。如果两个链表相交，那么它们从交点到链表末端的长度是相同的。通过让p和q分别遍历完两个链表，确保它们走过的总长度相同，这样就可以保证如果链表相交，p和q会在交点相遇。如果两个链表不相交，这种方式也会让p和q同时到达各自的末端null，因此可以正确返回null。

在此解法中，两个指针最终相遇的节点如果不是null，那么一定是交点。这是因为两个指针都走过了相同的距离——即两个链表的总长度，此时如果它们在非null节点相遇，只能是在交点相遇。如果两个链表不相交，两个指针会在链表末端的null处相遇，因此可以正确判断链表是否相交。

算法中，如果两个链表不相交，p和q将分别遍历完两个链表后指向对方的链表。因为两链表不相交，所以它们最终都会到达各自链表的末端null。由于两个指针的行走路径长度相同，它们会同时到达null，这时循环终止，并返回p（或q，此时p和q都是null），从而确保在不相交的情况下返回null。

此方法已经考虑了包括链表为空的情况。如果任一链表为空（即headA或headB为null），则while循环的初始条件`p != q`不成立，因为p和q都是null。循环不执行，直接返回p（或q），此时为null。因此，这种情况下算法正确地返回null，表示链表不相交。