160. Intersection of Two Linked Lists

[Shawngbk]

因为两个链表可能长度不同，但是如果都不为空则会相交一点，所以两个链表的出发点要相同。 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; int lenA = length(headA); int lenB = length(headB);

    // move headA and headB to the same start point

    while(lenA > lenB) {
        headA = headA.next;
        lenA --;
    }
    while(lenB > lenA) {
        headB = headB.next;
        lenB --;
    }

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

private int length(ListNode head) {
    int length = 0;
    while(head != null) {
        head = head.next;
        length ++;
    }
    return length;
}

HashSet解法 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null)return null; HashSet set = new HashSet<>(); while(headA != null){ set.add(headA); headA = headA.next; } while(!set.contains(headB) && headB != null){ headB = headB.next; } if(headB != null)return headB; return null; }