Java-NoTricks-O(l1+l2)


  • 3
    A
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA==null||headB==null) return null;
            int l1, l2;
            l1=l2=0;
            ListNode currA = headA;
            ListNode currB = headB;
            
            while(currA!=null){
                l1++;
                currA=currA.next;
            }
            while(currB!=null){
                l2++;
                currB=currB.next;
            }
            
            currA = headA;
            currB = headB;
            
            ListNode longer=null, shorter=null;
            int diff=0;
            
            if(l1>l2){
                longer=headA;
                shorter=headB;
                diff=l1-l2;
            } else {
                longer=headB;
                shorter=headA;
                diff=l2-l1;
            }
            
            for(int i=0; i<diff; i++){
                longer=longer.next;
            }
            
            while(longer!=shorter||(longer!=null&&shorter!=null)){
                if(longer==shorter) return longer;
                longer=longer.next;
                shorter=shorter.next;
            }
            return null;
        }
    

  • 0
    G

    I'm a bit confused on the last loop. Wouldn't

    if(longer == shorter) return longer;
    

    return incorrect nodes? For example, given the lists [1,2,3] and [1,4,5], it would return the node at value 1.


  • 0
    A

    Here we are comparing the references and not the int values of the nodes. So if(longer == shorter) return longer; will return true only if the two references point to the same node. When we talk about "intersection" here, we mean physical intersection of the lists and not just intersection of values contained in the list. if(longer.val == shorter.val) return longer; would've returned the node with value 1 in your example.


  • 0
    G

    Oh I see, that makes sense, thanks!


  • 0
    Y
        while(shorter != null)){
            if(longer == shorter) return longer;
            longer=longer.next;
            shorter=shorter.next;
        }
        return null;
    

    have some polish on the while loop


  • 0
    M

    @GreyHaven longer and shorter point to the same node. You can either return longer or shorter to get that node.


Log in to reply
 

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