链表 - LeetCode 52. 两个链表的第一个公共节点 🌟

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

image.png

注意：

如果两个链表没有交点，返回 null。在返回结果后，两个链表仍须保持原有的结构。可假定整个链表结构中没有循环。

程序尽量满足O(n) 时间复杂度，且仅用 O(1) 内存。

image.png

采用双指针

构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，指针 A , B同时开始运动，做如下操作：

image.png

指针 A , B 重合，并有两种情况：

• 若两链表有公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node
• 若两链表无公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA == null || headB == null) return null;
        ListNode A = headA, B = headB;
        // 如果是两个等长的不相交链表会不会死循环那 ??
        // 不会, 当指向到 null != null ,不合法循环条件就会执行return
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

复杂度分析：

• 时间复杂度 O(a+b) ： 最差情况下（即 ∣a−b∣=1 , c=0 ），此时需遍历 a+b 个节点。
• 空间复杂度 O(1) ： 节点指针 A , B 使用常数大小的额外空间。