【探索-中级算法】相交链表

注意题目要求的时间与空间复杂度。

只要保持交点之前移动的距离相等即可。即在遍历 A、B 的时候要同时从 a1 和 b2 开始，这样才能保证同时遍历到相交的 c1。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode tmpA = headA;
    ListNode tmpB = headB;
    int aCounts = 0;
    while (tmpA!=null) {
        ++aCounts;
        tmpA = tmpA.next;
    }
    int bCounts = 0;
    while (tmpB!=null) {
        ++bCounts;
        tmpB = tmpB.next;
    }
    tmpA = headA;
    tmpB = headB;
    // 如果 headA 的节点比 headB 的多
    if (aCounts>bCounts) {
    	// 移动 headA 的指针到合适的位置
        for (int i = 0; i < aCounts-bCounts; i++) {
            tmpA = tmpA.next;
        }
    } else {
        for (int i = 0; i < bCounts-aCounts; i++) {
            tmpB = tmpB.next;
        }
    }
    while (tmpA != null && tmpB != null) {
        if (tmpA==tmpB) return tmpA;
        else {
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }
    }
    return null;
}