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?

I'm using C++.

How could I Be able to:

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.

Answer 1

It looks like your own algorithm doesn't handle the number of occurrences of a number in the list, so it is not correct.

But the rest of your question suggests an algorithm that would work. Using a data structure similar to a hash table, you could record the number of occurrences for each number. Actually, many data structures would work, as long as the records stored in the data structure consist of
number:occurrences
Once you build this representation for two lists, you can easily do a comparison to see if they are equal.

Answer 2

I think you've got two different flavors of hash here. The solution with the two hash tables seems to be referring to a Perl-style hash table, otherwise known as an associative array. This is a structure which lets you use any arbitrary value (string, number, whatever, Perl is very weakly typed) as an array index.

In C or C++, a hash table uses a hash function to map strings to integers to facilitate searching. I suppose you could do something like that here, though it might not be the optimum solution. If the numbers are integers and their range is limited, you could just use the numbers themselves as array indices and put the number of occurances in the array. Other than that, I still like the sort and compare idea.