merge sort both lists: O(nlogn)
Now, for both lists to be identical, just compare the corresponding elements
in the lists i.e. L1(1) == L2(1), L1(2) == L2(2) ...
= O(n)
--Sundeep.
On Wed, Jun 2, 2010 at 10:47 PM, Raj N rajn...@gmail.com wrote:
@Antony: The 2 lists should have the same
construct bst from both list and check if the bst are equal by printing
their inorder traversal.
On 2 June 2010 22:47, Raj N rajn...@gmail.com wrote:
@Antony: The 2 lists should have the same elements as well the number must
be equal
On Wed, Jun 2, 2010 at 5:38 PM, Antony Vincent Pandian.S.
@ Raj,
Just to clarify, same elements refer to copy of identical data or link list
members pointing to same data ?
On Wed, Jun 2, 2010 at 10:47 PM, Raj N rajn...@gmail.com wrote:
@Antony: The 2 lists should have the same elements as well the number must
be equal
On Wed, Jun 2, 2010 at 5:38
simple in place O(n lg n) solution.
Choose a pivot in first array and partition it like in quicksort.
Find the pivot in second array and partition. Now recurse on both
halves. At any point if no of elements in array are not equal...
Abort!
--
--
But perhaps the elements in lists may not be in order.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Jun 3, 2010 at 6:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
simple in place O(n lg n) solution.
Choose a pivot in first array and partition it like in quicksort.
Find
Consider two linked lists l1 and l2. Create 2 hash maps,h1 and h2, one
for each list with the format, element, number of occurrence.
Traverse one element in each list at a time. For each element in list
l1, check whether it is present in h2. If yes, remove the element from
h2 if the number of
You can construct some kind of Search Tree like BST from the first list and
search for every element in the second list in that search Tree. O(NlogN)
time
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Wed, Jun 2, 2010 at 6:18 AM, sharad kumar aryansmit3...@gmail.comwrote:
@sharad kumar: But don't you think this'll consume a lot of space. Merge
sort will give O(nlogn) complexity when a separate LL is used to store the
sorted elements but if we disbuild the same LL it'll be O(n2). And also wat
do u mean by combining LL can u explain
On Wed, Jun 2, 2010 at 6:48 AM,
@Raj
What do you mean by identical? You are just concerned about the
presence of one element in another LL or you are concerned about the
equality of number of elements too?
On 6/2/10, Raj N rajn...@gmail.com wrote:
@sharad kumar: But don't you think this'll consume a lot of space. Merge
sort
@Antony: The 2 lists should have the same elements as well the number must
be equal
On Wed, Jun 2, 2010 at 5:38 PM, Antony Vincent Pandian.S. sant...@gmail.com
wrote:
@Raj
What do you mean by identical? You are just concerned about the
presence of one element in another LL or you are
Hi all,
Can someone suggest an efficient algorithm to check if 2 linked lists
are identical. If 2 lists have to be sorted then there'll be a lot of
space consumption for 2 separate linked lists. Can the whole process
be done O(n2)
--
You received this message because you are subscribed to the
@Raj:sorting can be done in O(nlogn)..sort both and compare both.or use a
hash map to store all elements of one LL and then compare it with
otheror combine both the LL perform merge sort and start deleting
adjacent elements.if adjacent elements in equal count then LL are equal and
at end of
12 matches
Mail list logo
