Вилучення дублікатів з невідсортованого списку

Задача

Вилучити елементи що повторюються з невідсортованого списку. Як це можна зробити якщо нема пам’яті для додаткового буфера?

Рішення з додатковим буфером

Достатньо просто зберігати елементи в хеш-таблиці і прибирати дублікати якщо елемент з поточним значенням вже є у хешу.

Рішення без додаткового буфера

У цьому випадку можна працювати з двома вказівниками: одни вказує на поточний елемент що ми його перевіряємо, другий – для порівняння з усіма попкркдніми елементами.

В списку з одного елемента всі елементи унікальні, тому перевірку можна почати з другого елемента. Якщо другий елемент є унікальним то тепер у нас 2 елементи з якими можна порівнювати. І так далі…

void RemoveDups(list* head)
{
    if (head == NULL) return;
    list* prev = head;
    list* cur = prev->next;
    while (cur)
    {
	for (list *run = head; run != cur; run = run->next)
	{
  		if (run->data == cur->data)
		{
			// remove current item
			list *tmp = cur->next;
			prev->next = tmp;
			delete cur;
			cur = tmp;
                }
	}
		 
	if (run == cur)
	{
	    prev = cur;
	    cur = cur->next;
	}
    }
}

Також дивись Як прибрати символи-дублікати з С-рядка

Залишити відповідь

Зайти з допомогою: