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

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

Примеры:

Input: 1 -> 2 -> 7 -> 3 -> 2 -> 5 -> 1
Output: 7 -> 3 -> 2 -> 5 -> 1
Explanation: 
Given Linked List: 1 -> 2 -> 7 -> 3 -> 2 -> 5 -> 1
Duplicate elements: 1, 2
Modified Linked List: 7 -> 3 -> 2 -> 5 -> 1

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 2 -> 3 -> 4 -> 5

Подход: выполните следующие шаги, чтобы решить проблему:

• Инициализируйте фиктивный узел и сделайте его следующей точкой head .
• Отменить указанный связанный список.
• Инициализируйте неупорядоченный набор, скажем, посещенный, чтобы сохранить уже посещенные узлы.
• Инициализируйте два узла, скажем , currnode, указывающий на фиктивный узел, и nextnode, чтобы сохранить следующий узел текущего узла.
• Переберите связанный список и проверьте, посещались ли уже данные следующего узла текущего узла или нет.
• Если он уже посещен, то выполните следующие действия:
  • Инициализируйте новый узел, скажем, повторяющийся , чтобы сохранить следующий узел , который в данном случае является дублирующим узлом.
  • Сделать текущую следующую точку следующей из следующего узла .
• В противном случае:
  • Вставьте данные nextnode в посещаемый набор.
  • Сделать nextnode текущим узлом .
• Наконец, отмените измененный связанный список и вернитесь.

Ниже приведена реализация вышеуказанного подхода:

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