[Java] My AC Solution: Align and Compare


  • 2
    F

    The basic idea is to get the length of each list first and skip all impossible nodes. Then we may compare nodes one by one till the intersection.

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int lenA = length(headA);
        int lenB = length(headB);
        int diff = Math.abs(lenA - lenB);
    
        if (lenA > lenB) 
            while(diff-- > 0) headA = headA.next;
        else 
            while(diff-- > 0) headB = headB.next;
    
        for (; headA != null && headB != null; headA = headA.next, headB = headB.next) 
            if (headA.val == headB.val) return headA;
        return null;
    }
    
    private int length(ListNode n) {
        if (n == null) return 0;
        int length = 0;
        while (n != null) {
            length++;
            n = n.next;
        }
        return length;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.