Читать нас в Telegram

Задача: написать код, удаляющий дубликаты из несортированного связного списка

Рубрика: Задачки
31 мая 2015 22:51
6748
3

Дополнительное задание. Как вы будете решать задачу, если запрещается использовать временный буфер?

Решение

Что бы удалить копии из связного списка, их нужно сначала найти. Для этого подойдет простая хэш-таблица. В приведенном далее решении выполняется проход по списку, каждый элемент которого добавляется в хэш-таблицу. Когда обнаруживается повторяющийся элемент, он удаляется, и цикл продолжает работу. За счет использования связного списка всю задачу можно решить за один проход.

public static void deleteDups (LinkedListNode n) {
		Hashtable table = new Hashtable();
		LinkedListNode previous = null;
		while (n != null) {
			if (table.containsKey(n.data)) {
				previous.next = n.next;
			} else {
				table.put(n.data, true);
				previous = n;
			}
			n = n.next;
		}
}

Приведенное решение потребует O(N) времени, где N – количество элементов в связном списке.

Дополнительное ограничение: использование буфера запрещено

В этом случае мы можем реализовать цикл с помощью двух указателей: current (работает через связный список) и runner (проверяет все последующие узлы на наличие дубликатов).

public static void deleteDups (LinkedListNode head) {
	if (head == null) return;

	LinkedListNode current = head;
	while (current != null) {
		/* Удаляем все следующие узлы с таким же значением */
		LinkedListNode runner = current;
		while (runner.next != null) {
			if (runner.next.data == current.data) {
				runner.next = runner.next.next;
			} else{
			  runner = runner.next;
			}
		}
		current = current.next;
	}
}

Данный код требует всего O(1) пространства, но занимает O(N2) времени.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»

Призы для программистов — нужно пройти опрос. Больше ответов — больше шансы

Темы: Массивы и строки
3