How do i know if two linked lists are set equal?
if L1 and L2 are linked lists
set equal meaning the set of values of the nodes in L1 is the same as the set of values of the nodes in L2 and order does not matter
i know it hasdo do with traversing the lists
Jump to PostIf you want the ability to compare even if they are not in the same order, but contain the same sets of data, when you overload your == operator you could temporarily sort the list and than compare.
Jump to PostBut you have forget one thing to compare node number in both the list.
It really depends on what a 'set' constitutes here. Remember, in its truest form, a set has no duplicates so converting an array (or list) to a set can change its size. For instance
If you want the ability to compare even if they are not in the same order, but contain the same sets of data, when you overload your == operator you could temporarily sort the list and than compare.
You traverse the first list. Let's say you're at element 0.
You check your second list until you find an element = element 0 from the first list. Two elements (nodes) are equal if all their fields are equal.
If you don't find an element from list2 = element 0 from list 1, the lists are not equal.
If you do find an element from list 2 = element 0 from list 1, you start the algorithm again for element 1 from list 1.
good logic @Buffalo101.
But you have forget one thing to compare node number in both the list.
@rockerjhr please add this line in above algorithm in first position
if number_of_first_list is not equal to number_of_second_list
then return (false) // means lists are not same..
else
/*
that code for checking node by node values..
*/
But you have forget one thing to compare node number in both the list.
It really depends on what a 'set' constitutes here. Remember, in its truest form, a set has no duplicates so converting an array (or list) to a set can change its size. For instance
List: [a,b,b,c,d,a,a,a]
Converts to
Set: [a,b,c,d]So the length of the first two lists is not necessarily an indicator of a failure condition.
How do i know if two linked lists are set equal?
There are a couple of suggestions above. If there is no need to worry about optimal runtime performance then they are probably just as easy to implement.
One way to do this in better than O(n*n) is to convert the lists to sorted arrays (possibly removing duplicates) and iterate the two resulting lists together comparing that they are equal.
In pseudocode, that looks something like:
L1 : 1 - 7 - 4 - 3 - 1
L2 : 4 - 1 - 7 - 4 - 3
sort_list L1 as S1 -> [1,3,4,7] # duplicates removed
sort_list L2 as S2 -> [1,3,4,7] # duplicates removed
return false unless length(S1) == length(S2)
while length(S1) > 0
a = S1.pop
b = S2.pop
return false unless a == b
return trueyes it would run for above example....
what i was suggesting, you have implement in your last post..
return false unless length(S1) == length(S2)
that is what i wanted to say you about checking the sets length first, which you forgot to mentioned in your earlier post...
this is very necessary, just take a look on below example..
L1 : 1 - 7 - 4 - 3 - 1
L2 : 4 - 1 - 7 - 4 - 3 - 50
It has one additional node in list L2, which shows difference in these list..
but any chance if you forget to put length condition it will return true.
which is wrong in our this case ... right?
but any chance if you forget to put length condition it will return true.
which is wrong in our this case ... right?
No. List contents can be condensed when converted to a set (due to duplicates being removed). Consider the following:
L1: 1 - 1 - 1 - 1 - 1 - 2
L2: 1 - 2
They are 'set equal'. This is, represented as sets, these two are equivalent; they both contain the values [1,2] . However, if you take the length of them you get length(L1) /= length(L2) which is not indicative of the set equality.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.