Question

Given two sorted lists, L1 and L2, write a procedure to compute L1 ∩ L2 using only the basic list operations.

Answer 1

This question asks you to write a function that returns the elements common to both sorted list.The following function achieves this:

List Intersect( List L1, List L2 )

{
Position L1_pos, L2_pos, Result_pos;
List Result;
L1_pos = L1->Next;
L2_pos = L2->Next;
Result_pos = Result = MakeEmpty();
while ( L1_pos != NULL && L2_pos != NULL )
{
if ( L1_pos->Element < L2_pos->Element )
L1_pos = L1_pos->Next;
else if ( L1_pos->Element > L2_pos->Element )
L2_pos = L2_pos->Next;
else
{
Insert( L1_pos->Element , Result , Result_pos );
L1_pos = L1_pos->Next;
L2_pos = L2_pos->Next;
Result_pos = Result_pos->Next;
}
}
return Result;
}

For the two linked lists L1 and L2, we assume that the length of L1 is n1 and the length
of L2 is n2. Then the running time of the above procedure is O(n1 + n2).