Is there a deterministic algorithm possible for the following:?

Question

INPUT: Two lists L1 and L2
QUESTION: Do L1 and L2 represent the same list?
(That is, do L1 and L2 contain the same numbers, each appearing exactly the same number of times?).

My Solution:
temp = head->L1
while search_L2(temp) == true
temp = temp->next
if search_L2(temp) == false
OUTPUT: L1 does not represent L2

Is this a correct algorithm?

Could this algorithm be a randomized algorithm (possibly using hash functions?). If so, how is it possible?

Answer 1

Your algorithm fails on a couple of points. First, it doesn't check duplicates; and second, it doesn't catch values in L2 that are not present in L1.

I think the best way to do this is to sort the lists, after first checking that they are the same length.

Answer 2

You would probably be better off using two hash tables. Populate these by traversing each list. Then, compare the keys in the hash tables to determine if they contain the same numbers. The key of the hash table can be the numbers in the list and the values can be the count of occurrences.

What language are you developing this in?

Answer 3

i think of you have have been given 2 different flavors of hash right here. the answer with the two hash tables looks bearing on a Perl-type hash table, in any different case favourite as an associative array. that's a shape which permits you to apply any arbitrary fee (string, quantity, in spite of, Perl is extremely weakly typed) as an array index. In C or C++, a hash table makes use of a hash function to map strings to integers to facilitate finding. i think you may do something like that right here, in spite of the undeniable fact that it may no longer be the optimal answer. If the numbers are integers and their selection is limited, you may basically use the numbers themselves as array indices and placed the style of occurances interior the array. different than that, I nonetheless like the type and evaluate concept.