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

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

Решение

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

			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 – Компанию»