输入两个链表，找出它们的第一个公共结点（BAT面试题）

一，题目描述
输入两个单链表找出它们的公共节点并返回该节点
示例：

输出： c1

二：解决思路：

1. 分别求两个链表的长度
2. 算出差值, 让长的链表先走差出的步数
3. 走完之后 headA 和 headB 已经在同一起跑线了
4. 同时先后遍历AB链表看AB是否相交

5. 语言	方法
   5712	d9rS1Kt1tg
   46Pcd	抖音养号秘籍
   7384	2007/03/22 17:29:05

三，代码实现

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 1. 分别求两个链表的长度
    int size1 = size(headA);
    int size2 = size(headB);
    // 2. 算出差值, 让长的链表先走
    if (size1 > size2) {
        int offset = size1 - size2;
        for (int i = 0; i < offset; i++) {
            headA = headA.next;
        }
    } else {
        int offset = size2 - size1;
        for (int i = 0; i < offset; i++) {
            headB = headB.next;
        }
    }
    // 3. 此时此刻, headA 和 headB 已经在同一起跑线了
    while (headA != null && headB != null) {
        // 比较的是节点是不是相同对象(比较身份)
        if (headA == headB) {
            // 如果相同节点, 认为这个位置就是链表的交点
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    // 链表不相交
    return null;
}