How do you remove duplicate odd numbers from a linked list?

Question

Requirements / Limitations:

• remove duplicates only
• save one copy
• the list is not sorted at first

How can this be implemented in C? (The algorithm and / or code will be very grateful!)

Answer 1

If the list is very long and you need reasonable actions, and you are fine with the distribution of additional log (n) memory, you can sort in nlog (n) using qsort or merge sort:

http://swiss-knife.blogspot.com/2010/11/sorting.html

Then you can remove duplicates in n (total: nlog (n) + n)

If your list is very tiny, you can do, for example, jswolf19, and you get: n (n-1) / 2 the worst.

Answer 2

I would either

• combines a list followed by a linear scan to remove duplicates
• use an insert-based algorithm that already removes duplicates when rebuilding a list.

The first will be faster, the latter will be easier to implement from scratch: just create a new list by pushing items from the old list and inserting them into the new one, scanning it until you click an item with a large value (in this case, you insert an item into the list) or an equal value ( in this case you delete the item).

Answer 3

There are several different ways to detect / remove duplicates:

Nested loops

Follow the next value sequentially, then scan to the end of the list to see if this value is again. This is O (n ² ) - although I believe that the boundaries can be stated below? - but the actual performance may be better since only scanning from i to end (not from 0 to end ) is performed, and it may end earlier. This does not require additional data, except for a few variables.

(See Christophe on how to do this simply by going around the linked list and destructively adding to the new list — for example, nested loops should not “feel” like nested loops.)

Sort and filter

Sort the list (mergesort can be modified to work with linked lists) and then detect duplicate values ​​(they will now be side by side). With good sorting, this is O (n * lg (n)). The sorting phase is usually / can be destructive (for example, you have a “single copy”), but it has been changed; -)

Scan and support search

Scan the list, and when scanning the list, add values ​​to search. If the search already contains the specified values, then there is a duplicate! This approach can be O (n) if access to the search is O (1). Usually, a hash / dictionary or set is used as the search, but if only a limited range of integrals is used, the array will work very well (for example, the index is a value). This requires additional storage, but there is no “additional copy” - at least in literal reading.

For small values ​​of n, large-0 is almost useless; -)

Happy coding.

Answer 4

Well, you can sort the list first and then check for duplicates, or you can do one of the following:

 for i from 0 to list.length-1 for j from i+1 to list.length-1 if list[i] == list[j] //delete one of them fi loop loop 

Answer 5

This is probably the most unoptimized piece of shit, but it will probably work.

Iterate through the list by holding the pointer to the previous object each time you go to the next. Inside your iteration loop, do all of this to check for duplicate. If there is a duplicate, now return to the main iteration loop, get the next object. Set the pointer of previous objects to the next object on the object that you just extracted, then exit the loop and restart the entire process until there are duplicates.

Answer 6

You can do this in linear time using a hash table.

You want to view the list sequentially. Every time you encounter an element with an odd number, look at it in your hash table. If this number is already in the hash table, remove it from the list, if not add it to the hash table and continue.

Basically, the idea is that for each item that you are viewing in the list, you can check the constant time to see if this is a duplicate of the previous item that you saw. It takes only one pass through your list and in the worst case will have a linear amount of memory (in the worst case, each list item is a unique odd number, so your hash table as long as your list).