第8周作业

leetcode的160题：

暴力的和hash的两个方案

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode initialHeadB=headB;
    while (headA != null){
        while (headB != null){
            if (headA.equals(headB)) return headA;
            headB=headB.next;
        }
        headA = headA.next;
        headB = initialHeadB;
    }
    return null;  
}

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    HashSet hA = new HashSet();
    while (headA != null) {
        hA.add(headA);
        headA = headA.next;
    }
    while (headB != null) {
        if (hA.contains(headB)) return headB;
        headB = headB.next;
    }
    return null;
}

去掉a和b的长度差开始循环比较

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        int len1 = 0;
        int len2 = 0;
        ListNode a = headA, b = headB;
        while (a != null) {
            a = a.next;
            len1++;
        }
        while (b != null) {
            b = b.next;
            len2++;
        }
        a = headA;
        b = headB;
        if (len1 > len2) {
            int num = len1 - len2;
            while (num > 0) {
                a = a.next;
                num--;
            }
        } else {
            int num = len2 - len1;
            while (num > 0) {
                b = b.next;
                num--;
            }
        }
        while (a != null) {
            if (a == b) return a; //没有说这是个有序或者无重复的单链表，
                                  // 因此涉及到的判断必须是(a == b) , 而不是 (a.val == b.val)
            else {
                a = a.next;
                b = b.next;
            }
        }
        return null;
    }

找了一个非常巧妙的方法

如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此，我们必须消除两个链表的长度差

指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置

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;
}