剑指 Offer 52. 两个链表的第一个公共节点

描述

输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：

在节点 c1 开始相交。

样例

示例 1：

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

示例 2：

输入：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。

提示

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路

只有当链表 headA 和headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。
当链表headA 和 headB 都不为空时，创建两个指针pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

• 每步操作需要同时更新指针pA 和 pB。
• 如果指针 pA 不为空，则将指针pA 移到下一个节点；如果指针 pB 不为空，则将指针pB 移到下一个节点。
• 如果指针 pA 为空，则将指针pA 移到链表headB 的头节点；如果指针pB 为空，则将指针 pB 移到链表 headA 的头节点。
• 当指针pA 和pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

1. 考虑不相交的情况，pA,pB 一定会在遍历完 A, B 链表时 同时 为 null ,此时 pA == pB ,退出循环，返回 pA(null)
2. 对于相交的情况，当 pA == pB 时，一定是相交点，返回 pA 就可以了。

AC代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

时间复杂度

时间复杂度：O(m+n)O(m+n)，其中 mm 和 nn 是分别是链表 \textit{headA}headA 和 \textit{headB}headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

空间复杂度：O(1)O(1)。