[Java] My AC Solution: Sum up and minus the differences


  • 0
    D

    The idea is going through both list and sum up. Then minus one node at a time for which is bigger.

    You'll get the intersection if two number are the same. That's also the sum of those same nodes :)

    public class Solution {
     public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       	 if(headA==null||headB==null)return null;
       	 ListNode a=headA;
         ListNode b=headB;
         int ca=0,cb=0;        //count the sum
           while(a!=null||b!=null){
    			if(a!=null){
                	ca+=a.val;
    				a=a.next;
    			}
    			if(b!=null){
    				cb+=b.val;
    	           	b=b.next;
    			}
    		}
            a=headA;
            b=headB;
            while(ca>0&&cb>0){
           	 if(ca==cb&&a==b)return a;
           	 else if(ca>cb){
           		 ca-=a.val;
           		 a=a.next;
           	 }else{
           		 cb-=b.val;
           		 b=b.next;
           	 }
            }
            return null;
        }
    

    }


  • 0
    A
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA==null || headB==null) return null;
            int lenA = 1;
            ListNode a = headA;
            for(;a.next!=null;a=a.next) lenA++;
            int lenB = 1;
            ListNode b = headB;
            for(;b.next!=null;b=b.next) lenB++; // calculate length of A and B
            if (a!=b) return null;  // no intersection
            int pad = Math.abs(lenA-lenB); // length we have to pad
            a = lenA>lenB?headA:headB;  // a is longer list
            b = a==headA?headB:headA;  // b is shorter list 
            for(;pad!=0;pad--) a=a.next; // now a b are in the 
            for(;a!=b;a=a.next) b=b.next; // same distance with intersection
            return a;
        }
    

    similar idea, but kind of shorter writing


  • -1
    G

    I am surprised that the Judge is accepting OP's solution. The OP's code would fail for a simple test cases like this:

    // When both a,b are at 1 .... ca=cb and ta=tb, code returns 1
    headA : 1 -> 3 -> 2 -> NULL
    headB : 1 -> 2 -> 3 -> NULL
    
    // When both a,b are at 1 .... ca=cb and ta=tb, code returns 1
    headA : 1 -> 3 -> 3 -> NULL
    headB : 1 -> 2 -> 4 -> NULL
    
    // When both a,b are at 1 .... ca=cb and ta=tb, code returns 1
    headA : 5 -> 6 -> 1 -> 3 -> 2 -> NULL
    headB : 6 -> 5 -> 1 -> 2 -> 3 -> NULL

Log in to reply
 

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