leetcode-160 相交链表(IntersectionOfTwoLinkedLists)-java

题目：相交链表

编写一个程序，找到两个单链表相交的起始节点。

例如，下面的两个链表：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始相交。

注意：

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

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null)
        return null;

    int headALength = 0;
    int headBLength = 0;

    ListNode p = headA;
    while (headA != null){
        ++ headALength;
        headA = headA.next;
    }
    p = headB;
    while (headB != null){
        ++ headBLength;
        headB = headB.next;
    }

    while (headALength > headBLength) {
        headA = headA.next;
        headALength --;
    }

    while (headBLength > headALength) {
        headB = headB.next;
        headBLength --;
    }

    while (headA != null) {
        if (headA == headB)
            return headA;
        headA = headA.next;
        headB = headB.next;
    }
    return null;
}

边界值判断：

headA == null || headB == null    //有空链表，一定没有相交节点，返回null

变量注释：

headALength    //headA链表的节点数，相当于长度

headBLength    // headB链表的节点数

p    //ListNode类型，临时变量，作为循环变量使用

解题思路：（用题目给的例子解释）

首先有一点非常重要，相交节点后的所有节点 (包括相交节点) 都是两个链表共享的。

我们将两个链表的右端对齐，长度较大的链表 的左端的 多出来的节点 肯定不是相交节点，所以我们不考虑左端的这一部分的节点。

A ：          a1 -> a2  -> c1 -> c2 -> c3

B ： b1 -> b2 -> b3 -> c1 -> c2 -> c3

headALength = 5 ， headBLength = 6， B链表的长度较大

右端对齐，B的左端不考虑，也就是不考虑 节点b1

A从a1开始， B从b2开始，同时往右遍历，逐一比较，比较a1 和 b2 ， a2 和 b3 ... ...

遍历到的第一个  相同的节点，就是两个链表相交的起始节点（相交节点）

代码解释：

第1,2个循环是  计算headA 和 headB 两个链表的长度

第3,4个循环是  将headA 和 headB 移到要进行节点比较的位置   //只需移动长度较大的链表

第5个循环是  进行节点比较，如果有相同节点，直接返回该相交节点