Следующий больший элемент в циклическом связанном списке

Для циклического односвязного списка задача состоит в том, чтобы напечатать следующий больший элемент для каждого узла в связанном списке. Если для какого-либо узла нет следующего большего элемента, выведите «-1» для этого узла.

Примеры:

Input: head = 1 → 5 → 2 → 10 → 0 → (head)
Output: 5 10 10 -1 -1
Explanation:
The next greater elements of each node are:

1. Node 1: Next greater element is 5.
2. Node 5: Next greater element is 10.
3. Node 2: Next greater element is 10.
4. Node 10: No next greater element exists. Therefore print “-1”.
5. Node 0: No next greater element exists. Therefore print “-1”.

Input: head = 1 → 5 → 12 → 10 → 0 → (head)
Output: 5 12 -1 12 -1

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

• Инициализируйте переменную Node, скажем, res как NULL, чтобы сохранить головной узел связанного списка, представляющий следующий больший элемент.
• Кроме того, инициализируйте переменную узла, скажем, tempList как NULL, чтобы выполнить итерацию по связанному списку, представляющему следующий больший элемент.
• Пройдитесь по круговому связанному списку и выполните следующие шаги:
  • Инициализируйте узел, скажем, curr , чтобы сохранить ссылку на текущий узел кругового связанного списка.
  • Инициализируйте переменную, скажем, Val как -1 , чтобы сохранить значение следующего большего элемента текущего узла .
  • Выполняйте следующие шаги до тех пор, пока curr не будет равен ссылке текущего узла кругового связанного списка:
    • Если значение в текущем узле curr больше, чем значение текущего узла кругового связанного списка, присвойте значение curr.data Val и прервите цикл.
    • Обновите значение узла curr как curr = curr.next .
  • Если узел res равен NULL , создайте новый узел со значением Val и назначьте его res , а затем присвойте значение res tempList .
  • В противном случае создайте новый узел со значением Val и назначьте его tempList.next , а затем обновите узел tempList как tempList = tempList.next.
• После выполнения вышеуказанных шагов распечатайте элементы связанного списка res в качестве ответа.

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

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