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; }