Accepted java solution, O(n+m) time, O(n) memory


  • 1
    V

    public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        if(headA == null ||  headB == null ){
            return null;
        }
        
        
        int lengthA = 0;
        int lengthB = 0;
        ListNode Alength = headA;
        ListNode Blength = headB;
    
        //calculate the length of A and B
        while(Alength != null){
            lengthA++;
            Alength = Alength.next;
        }
        while(Blength != null){
            lengthB++;
            Blength = Blength.next;
        }
        
        //move the head of the longer list so they have the same length of tails.
        if(lengthA > lengthB){
            int move = lengthA - lengthB;
            for(int i = 0; i < move; i++){
                headA = headA.next;
            }
        }else{
            int move1 = lengthB - lengthA;
            for(int j = 0; j < move1; j++){
                headB = headB.next;
            }
        }
        
       // if headA == headB, there is the intersection point
        while(headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    

    }


Log in to reply
 

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