Интервью: Найти похожие элементы из двух связанных списков и вернуть результат в виде связанного списка

Question

Этот вопрос был задан в интервью для моего друга.Интервьюер попросил найти алгоритм и кодировать его на языке Java

Вопрос: Найти похожие элементы из двух связанных списков и вернуть результат в виде связанного списка

Например: если связанный список1имеет 1-> 2-> 3-> 4-> 4-> 5-> 6 и связанный список 2 имеет 1-> 3-> 6-> 4-> 2-> 8

Результирующий связанный список 1->2-> 3-> 4-> 6

Спасибо

Answer 1

Как насчет:

return new LinkedList(new LinkedHashSet(list1).retainAll(list2));

Это сохраняет порядок как в list1. Конечно, кто-то может жаловаться на то, что это мошенничество, если спрашивающий имел в виду, что вы должны построить алгоритм самостоятельно, но если единственным ограничением было «закодировать его в Java», то это верное решение (и, скорее всего, более эффективное и бесплатно, чем чье-либо решение более низкого уровня).

Answer 2

Создание хеш-таблицы.
Пройдите по первому списку ссылок, отметьте записи по мере их посещения.O (N) Пройдите по второму списку ссылок, пометьте записи (другой флаг и т. Д.), Когда вы посещаете их.O (M)

Пройдите по хеш-таблице и найдите все записи с обоими членами LL.Создайте новых членов LL, как вы найдете записи.O (H)

Общая сложность: O (N) + O (M) + O (Макс. (N, H, M)) => O (N)

Примечание. Отредактированный ответдля Саураба.

Answer 3

получить первый связанный список и начать с первого элемента, сравнить его с первым элементом второго связанного списка, если они совпадают, добавить значение к результату и перейти ко второму элементу первого списка, в противном случае перейдите к второй элемент второго списка, делайте это до тех пор, пока значения не станут одинаковыми или пока не дойдете до второго списка.

Answer 4

Использование HashSet для постоянной работы содержит время.

Итерация по первому списку и добавление их в HashSet --- O (n) (Примечание добавление в HashSet является постоянным временем)

Выполните итерацию по второму списку и, если hashSet.contains, добавьте их в список результатов.

В конце цикла вернуть список результатов