Wednesday, April 1, 2009

Efficient Algorithm to remove duplicate elements in a linked list

Remove duplicate elements in a linked list
Write an efficient algorithm to remove duplicate elements in a linked list.
I/p : 4->5->6->4->4->7->5->3
O/p :4->5-> 6->7->3

Will This Work?
Time complexity to construct a BST is o(n)2.

How About Heap??
instead of BST, if we construct a heap,
its time complexity 0(n) for construction.

Construct a min heap,
1. delete the min. element, and use it for insertion into the list.

2. while inserting the element, check with its previous element,
if it exists in the list, then dont add that element to the list.

If not exists, add that elemtn to the list.

3. Now repeat the process, until all elemtns complete.

Now complexity:

space complexity: 0(n)
time complexity: 0(n) for heap construction
0(1) for list construction,--we are checking with last elemtn in the list.

0(logn) for element deletion in heap. and to adjust the heap.

so overall time complexity is 0(n).

please correct me, if any thing wrong.

Thank you

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.