Java-программа для перемещения всех вхождений элемента в конец связанного списка

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

Примеры:

Input  : 1 -> 2 -> 2 -> 4 -> 3
         key = 2 
Output : 1 -> 4 -> 3 -> 2 -> 2

Input  : 6 -> 6 -> 7 -> 6 -> 3 -> 10
         key = 6
Output : 7 -> 3 -> 10 -> 6 -> 6 -> 6

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

Временная сложность: O(n ² )

Эффективное решение 1: сохранить два указателя:
pCrawl => Указатель для обхода всего списка один за другим.
pKey => Указатель на вхождение ключа, если ключ найден. В остальном то же, что и pCrawl.
Мы начинаем оба вышеуказанных указателя с головы связанного списка. Мы перемещаем pKey только тогда, когда pKey не указывает на ключ. Мы всегда перемещаем pCrawl . Таким образом, когда pCrawl и pKey не совпадают, мы должны найти ключ, который находится перед pCrawl , поэтому мы переключаемся между pCrawl и pKey и перемещаем pKey в следующее место. Инвариант цикла заключается в том, что после замены данных все элементы от pKey до pCrawl являются ключами.

Ниже приведена реализация этого подхода.

Выход:

Before moveToEnd(), the Linked list is
10 20 10 30 40 10 60 

After moveToEnd(), the Linked list is
20 30 40 60 10 10 10

Сложность времени: O (n) требует только одного обхода списка.

Вспомогательное пространство: O(1)

Эффективное решение 2:
1. Пройдитесь по связанному списку и наведите указатель на хвост.
2. Теперь проверьте наличие ключа и node->data. Если они равны, переместите узел к последнему-следующему, иначе двигайтесь вперед.

Выход:

Linked List before operations :
5 2 2 7 2 2 2 
Linked List after operations :
5 7 2 2 2 2 2

Временная сложность: O(n), где n представляет размер данного списка.
Вспомогательное пространство: O(1), дополнительное пространство не требуется, поэтому это константа.

Спасибо Равиндеру Кумару за предложение этого метода.

Эффективное решение 3: вести отдельный список ключей. Мы инициализируем этот список ключей пустым. Проходим по заданному списку. Для каждого найденного ключа мы удаляем его из исходного списка и вставляем в отдельный список ключей. Наконец, мы связываем список ключей в конце оставшегося заданного списка. Временная сложность этого решения также равна O(n) и требует только одного обхода списка.

Пожалуйста, обратитесь к полной статье о перемещении всех вхождений элемента в конец связанного списка для получения более подробной информации!