A different approach with O(n) time and O(1) space


  • 0
    S
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int size1=0,size2=0;
    		ListNode temp = null;
    		if(headA!=null ){
    			size1=1;
    		    for(temp =headA;temp.next!=null;size1++){
    		    		temp=temp.next;
    		    	}
    		}
    		if(headB!=null ){
    			size2=1;
    		    	for(temp =headB;temp.next!=null;size2++){
    		    		temp=temp.next;
    		    	}
    		}
    		if(size1>size2){
    			temp=headA;
    			ListNode temp2=headB;
    			for(int i=0;i<(size1-size2);i++){
    				temp=temp.next;
    			}
    			if(temp==temp2){
    				return temp;
    			}
    			for(int i=0;i<size2;i++){
    				if(temp.next==temp2.next){
    					return temp.next;
    				}
    				temp=temp.next;
    				temp2=temp2.next;
    			}
    		} else{
    			temp=headB;
    			ListNode temp2=headA;
    			for(int i=0;i<(size2-size1);i++){
    				temp=temp.next;
    			}
    			if(temp==temp2){
    				return temp;
    			}
    			for(int i=0;i<size1;i++){
    				if(temp.next==temp2.next){
    					return temp.next;
    				}
    				temp=temp.next;
    				temp2=temp2.next;
    			}
    		}
          return temp;  
        }

Log in to reply
 

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