If data structure augmentation and designing algorithms give you a high and you wish to post in this forum email me(Inder) at inder.pall@gmail.com
DISCLAIMER : questions posted here could be from multiple source, i'll try my best to provide credit.
1. scan the first list and prepare a map with member as key and a counter initialized to 1 as value. Whenever you have duplicate key increment the counter. 2. scan the second list and for each member check if map prepared earlier contains that key: 2.1 if key does not exist, exit, lists are not same. 2.2 if key exists, decrement the counter associated with it. if counter goes negative, exit, lists are not same.
3. scan the first list again and check counter in the map for each member, anytime counter is positive, exit, lists are not same.
I don't think a map is needed in this case. This problem can be solved in O(1) space and linear time O(min(n,m)).
Start iterating from the head of both the lists simultaneously. At each iteration, compare the nodes of both the lists. If they are same, move ahead else return FALSE.
At the end, if all nodes are found equal (and both lists are of equal length), return TRUE.
3 comments:
1. scan the first list and prepare a map with member as key and a counter initialized to 1 as value. Whenever you have duplicate key increment the counter.
2. scan the second list and for each member check if map prepared earlier contains that key:
2.1 if key does not exist, exit, lists are not same.
2.2 if key exists, decrement the counter associated with it. if counter goes negative, exit, lists are not same.
3. scan the first list again and check counter in the map for each member, anytime counter is positive, exit, lists are not same.
4. if program reaches here, lists are same.
Also, check if they point to the same address before you start traversing.
I don't think a map is needed in this case. This problem can be solved in O(1) space and linear time O(min(n,m)).
Start iterating from the head of both the lists simultaneously. At each iteration, compare the nodes of both the lists. If they are same, move ahead else return FALSE.
At the end, if all nodes are found equal (and both lists are of equal length), return TRUE.
Post a Comment