Answer to Question #59996 in Java | JSP | JSF for özgür

Question

Given two linked lists L, M that contain integer keys in sorted order, provide the pseudo code of a function to create a new list that contains L ∩ M in sorted order. Your function should traverse the two lists only once

Answer 1

Pseudocode:

LinkedList<Integer> intersection(LinkedList<Integer> L,LinkedList<Integer> M){
           Initialize Integer LinkedList N;
           if (L is not empty AND M is not empty){
           init i = 0;         
           init j = 0;         
           while(i < L size AND j < M size){  
           if(L[i] == M[j]){
           N add L[i];
           i++;
           j++;
           }else{
           if(L[i] < M[j]){
           i++;
           }else{
              j++;                 
           }             
       }         
    }     
 }     
return N; 
}

Java code:

LinkedList<Integer> intersection(LinkedList<Integer> L, LinkedList<Integer> M){
            LinkedList<Integer> N = new LinkedList<Integer>();
              if(!(L.isEmpty() && M.isEmpty())) {
                   int i = 0;
                   int j = 0;
                   while(i < L.size() && j < M.size()){            
                   if(L.get(i) == M.get(j)){
                   N.add(L.get(i));
                        i++;
                        j++;            
                   }else{
                   if(L.get(i) < M.get(j)){                    
                       i++;
                  }else{
                       j++;                 
                }             
            }         
        }     
    }     
return N; 
}